数论傻谈

颓废之余写的怕记不得随便写

CF870F Paths

首先分类

\(\gcd(a,m)=d,设a=a_0d,m=m_0d\)

\(a_0d\bmod m_0d=dk\)

\(\Rightarrow a\bmod m=d(a_0\bmod m_0)\)

什么智障问题

关于exlucas​

求\(\binom{m}{n}\bmod m\),其中\(m\)不为质数

考虑对\(m\)质因数分解\(m=\prod\limits_{i=1}^{k}p_i^{a_i}\)，利用\(CRT\),即求\(\binom{m}{n}\bmod p_i^{a_i}\)

\(\binom{m}{n}\bmod p^{a}\)展开可化为\(\dfrac{n!}{m!(n-m)!}\bmod p_i^{a}\)

由于\(p^a\)不为质数且不与\(n!\)互质，所以依旧无法使用逆元，所以考虑消去阶乘中的\(p\)

即\(n!=\dfrac{n!}{p^x}p^x\),其中\(\dfrac{n!}{p^x}\)与\(p\)的互质，形象一点就是把\(n!\)中是\(p\)的倍数的\(i\)消去以达到逆元的效果，最后再乘回去

设\(f(n)为\dfrac{n!}{p^x},g(n)为x\)(\(f\)是去除\(p\)的结果,\(g\)是去除的个数让后面加回来)

考虑将阶乘展开\(\prod\limits_{i=1}^ni=p^{\dfrac{n}{p}}(\dfrac{n}{p})!\prod\limits_{i=1,i\bmod p\neq0}i\)

注意到后面的连乘具有循环节(取模时模数较小)

而\((\dfrac{n}{p})!\)中可能还包含\(p\)的因数

所以\(f(n)=f(\dfrac{n}{p})(\prod\limits_{i=1,i\bmod p\neq 0}^{p^k}i)^{\dfrac{n}{p^k}}\prod\limits_{i=1}^{n\bmod p^k}i,g(n)=\dfrac{n}{p}+g(\dfrac{n}{p})\)

注意如果多次询问可以预处理循环节

时间复杂度\(O(\sqrt{p}+\log_{p}n\sum p^k)\)

#include<bits/stdc++.h>
#define int long long
using namespace std;
int cnt_prime;
int prime[105];
int Num[105];
int Pow(int a,int b,int p)
{
	int base=a;
	int res=1;
	while(b)
	{
		if(b&1){
			res=((long long)res*base)%p;
		}
		base=((long long)base*base)%p;
		b>>=1;
	}
	return res;
}
int Ex_x,Ex_y;
int Ex_gcd(int a,int b)
{
	if(!b)
	{
		Ex_x=1;
		Ex_y=0;
		return a;
	}
	int Rex=Ex_gcd(b,a%b);
	int t=Ex_x;
	Ex_x=Ex_y;
	Ex_y=t-(a/b)*Ex_y;
	return Rex;
}
int inv(int a,int p)
{
	int d=Ex_gcd(a,p);
	Ex_x=(Ex_x+(p))%p;
	return Ex_x;
}
pair<int,int>cal(int n,int p,int pk)
{
	if(!n)
	{
		return make_pair(1,0);
	}
	int Ind=(n/pk);
	int rest=(n%pk);
	int Bas=1;
	for(int i=1;i<=pk;i++)
	{
		if(i%p)
		{
			Bas=((long long)Bas*i)%pk;
		}
	}
	Bas=(Pow(Bas,Ind,pk));
	for(int i=1;i<=rest;i++)
	{
		if(i%p)
		{
			Bas=((long long)Bas*i)%pk;
		}
	}
	pair<int,int>Nx=cal(n/p,p,pk);
	return make_pair(((long long)Nx.first*Bas)%pk,Nx.second+(n/p));
}
int get(int n,int m,int p,int k)
{
	int pk=Pow(p,k,1e9);
//	printf("%lld\n",pk);
	pair<int,int>Fn=cal(n,p,pk);
	//printf("%d %d %d\n",n,Fn.first,Fn.second);
	pair<int,int>Fm=cal(m,p,pk);
	pair<int,int>Fx=cal(n-m,p,pk);
	int Res=Fn.first;
	Res=((long long)Res*inv(Fm.first,pk))%pk;
	Res=((long long)Res*inv(Fx.first,pk))%pk;
	int Ind=(Fn.second-Fm.second-Fx.second);
	if(Ind>=k)
	{
		return 0;
	}
	Res=((long long)Res*Pow(p,Ind,pk))%pk;
//	printf("%lld %lld %lld %lld\n",Fn.first,inv(Fm.first,pk),inv(Fx.first,pk),Pow(p,Ind,pk));
	return Res;
}
int Exlucas(int n,int m,int p)
{
	cnt_prime=0;
	int X=p;
	for(int i=2;i*i<=X;i++)
	{
		if(X%i==0)
		{
			int tot=0;
			while(X%i==0)
			{
				X/=i;
				tot++;
			}
			prime[++cnt_prime]=i;
			Num[cnt_prime]=tot;
		}
	}
	if(X>1)
	{
		prime[++cnt_prime]=X;
		Num[cnt_prime]=1;
	}
	int M=p;
	int res=0;
	for(int i=1;i<=cnt_prime;i++)
	{
		int mi=Pow(prime[i],Num[i],M+1);
		int a=get(n,m,prime[i],Num[i]);
		//printf("%lld\n",a);
		int Mi=(M/mi);
		int Gcd=Ex_gcd(Mi,mi);
		Ex_x=((long long)Ex_x+mi)%mi;
		res=((long long)res+((((long long)Ex_x*Mi)%M)*a)%M)%M;
	}
	return res;
}
int n,m,p;
signed main()
{
	scanf("%lld %lld %lld",&n,&m,&p);
	printf("%lld",Exlucas(n,m,p));
}

关于类欧几里得算法

关于f

关于g,h

在做下面的情况之前首先推个结论

利用上面的公式展开平方项

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int MOD=998244353; 
int Ex_x,Ex_y;
int Pow(int a,int b,int p)
{
	int base=a;
	int res=1;
	while(b)
	{
		if(b&1){
			res=((long long)res*base)%p;
		}
		base=((long long)base*base)%p;
		b>>=1;
	}
	return res;
}
int inv(int a,int p)
{
	return Pow(a,p-2,p);
}
int inv2,inv6;
struct Euclid_Like{
	int h,f,g;
	Euclid_Like()
	{
		h=0;
		f=0;
		g=0;
	}
	void print()
	{
		printf("%lld %lld %lld\n",f,g,h);
	}
};
Euclid_Like cal(int n,int a,int b,int c)
{
	Euclid_Like Res;
	int Sumf=0;
	int Sumh=0;
	int Sumg=0;
	if(a==0)
	{
		Sumf=(n+1)%MOD;
		Sumf=(Sumf*(b/c))%MOD;
		
		Sumg=(n+1)%MOD;
		Sumg=(Sumg*(b/c))%MOD;
		Sumg=(Sumg*(b/c))%MOD;
		
		Sumh=(b/c)%MOD;
		Sumh=(Sumh*n)%MOD;
		Sumh=(Sumh*(n+1))%MOD;
		Sumh=(Sumh*inv2)%MOD;
		
		Res.f=Sumf;
		Res.g=Sumg;
		Res.h=Sumh;
	//	printf("%lld %lld %lld %lld\n" ,n,a,b,c); 
	//	Res.print();
		return Res;
		 
	}
	if((a>=c)||(b>=c))
	{
		Euclid_Like Lax=cal(n,a%c,b%c,c); 
		Sumf=((a/c)*(n%MOD))%MOD;
		Sumf=(Sumf*((n+1)%MOD))%MOD;
		Sumf=(Sumf*inv2)%MOD;
		Sumf=(Sumf+(((n+1)%MOD)*(b/c))%MOD)%MOD;
		Sumf=(Sumf+Lax.f)%MOD;
		
		Sumg=((b/c)*(b/c))%MOD;
		Sumg=(Sumg*(n+1)%MOD)%MOD;
	//	printf("%lld-\n",Sumg);
		int Nssx;
		Nssx=((a/c)*(a/c))%MOD;
		Nssx=(Nssx*(n)%MOD)%MOD;
		Nssx=(Nssx*(n+1)%MOD)%MOD;
		Nssx=(Nssx*(2*n+1)%MOD)%MOD;
		Nssx=(Nssx*inv6)%MOD;
		Sumg=(Sumg+Nssx)%MOD;
	//	printf("%lld--\n",Sumg);
		Nssx=((n+1)%MOD)%MOD;
		Nssx=(Nssx*n)%MOD;
		Nssx=(Nssx*(b/c))%MOD;
		Nssx=(Nssx*(a/c))%MOD;
		Sumg=(Sumg+Nssx)%MOD;
	//	printf("%lld----\n",Sumg);
		Nssx=Lax.f;
		Nssx=(Nssx*2)%MOD;
		Nssx=(Nssx*(b/c))%MOD;
		Sumg=(Sumg+Nssx)%MOD;
		Nssx=Lax.h;
		Nssx=(Nssx*2)%MOD;
		Nssx=(Nssx*(a/c))%MOD;
		Sumg=(Sumg+Nssx)%MOD;
		Nssx=Lax.g;
		Sumg=(Sumg+Nssx)%MOD;
		
		Nssx=Lax.h;
		Sumh=Nssx;
	//	printf("%lld-\n",Sumh);
		Nssx=(b/c);
		Nssx=(Nssx*n)%MOD;
		Nssx=(Nssx*(n+1)%MOD)%MOD;
		Nssx=(Nssx*inv2)%MOD;
		Sumh=(Sumh+Nssx)%MOD;
	//	printf("%lld--\n",Sumh);
		Nssx=(a/c);
		Nssx=(Nssx*(n)%MOD)%MOD;
		Nssx=(Nssx*(n+1)%MOD)%MOD;
		Nssx=(Nssx*(2*n+1)%MOD)%MOD;
		Nssx=(Nssx*inv6)%MOD;
		Sumh=(Sumh+Nssx)%MOD;
	//	printf("%lld---\n",Sumh);
		Res.f=Sumf;
		Res.g=Sumg;
		Res.h=Sumh;
	//	printf("%lld %lld %lld %lld\n" ,n,a,b,c); 
	//	Res.print();
		return Res;
	}
	else
	{
		int M=(a*n+b)/c;
	//	printf("%lldXSHWOSHINIDEGOU\n",M);
		Euclid_Like Lax=cal(M-1,c,c-b-1,a);
		Sumf=(n*(M)%MOD)%MOD;
		Sumf=(Sumf-Lax.f+MOD)%MOD;
		
		Sumg=(n*(M)%MOD)%MOD;
		Sumg=(Sumg*(M+1)%MOD)%MOD;
	//	printf("%lld-\n",Sumg);
		int Nssx;
		Nssx=Lax.h;
		Nssx=(Nssx*2)%MOD;
		Sumg=(Sumg-Nssx+MOD)%MOD;
	//	printf("%lld--\n",Sumg);
		Nssx=Lax.f;
		Nssx=(Nssx*2)%MOD;
		Sumg=(Sumg-Nssx+MOD)%MOD;
	//	printf("%lld---\n",Sumg);
		Nssx=Sumf;
		Sumg=(Sumg-Nssx+MOD)%MOD;
	//	printf("%lld---\n",Sumg);
		
		Sumh=(n*(M)%MOD)%MOD;
		Sumh=(Sumh*(n+1)%MOD)%MOD;
		Nssx=Lax.g;
		Sumh=(Sumh-Nssx+MOD)%MOD;
		 Nssx=Lax.f;
		Sumh=(Sumh-Nssx+MOD)%MOD;
		Sumh=(Sumh*inv2)%MOD;
		Res.f=Sumf;
		Res.g=Sumg;
		Res.h=Sumh;
	//	printf("%lld %lld %lld %lld\n" ,n,a,b,c); 
	//	Res.print();
		return Res;
	}
	                    	
} 
int t;
int n,a,b,c;
signed main()
{
	inv2=inv(2,MOD);
	inv6=inv(6,MOD);
	scanf("%lld",&t);
	while(t--)
	{
		scanf("%lld %lld %lld %lld",&n,&a,&b,&c);
		Euclid_Like RP=cal(n,a,b,c);
		RP.print(); 
	}
}
//1
//1 6 2 3

关于阶与原根

阶

设\(x\)为使得\(a^x\equiv1(\bmod m)\)最小的\(x\)，且\(\gcd(a,m)=1\),称\(x\)为\(a\)在\(\bmod m\)意义下的阶,记作\(Ord_ma=x\)

\(Quality1:\)\(a^x\equiv1(\bmod m)\)的充要条件是\(Ord_ma|x\)

充分性:\(a^x\equiv1\equiv a^{Ord_ma}(\bmod m)\)

\(m|a^{Ord_ma}-a^{x}\Rightarrow m|a^x(a^{Ord_ma-x}-1)\)

\(\because\gcd(a,m)=1,\gcd(a^x,m)=1\)

\(\therefore m|a^{Ord_ma-x}-1,a^{Ord_ma-x}\equiv1(\bmod m)(???)\)

设\(x=Ord_ma\times p+r(0\leq r<Ord_ma)\)

\(m|a^{x}-a^{{Ord_ma}}\Rightarrow m|a^{{Ord_ma}}(a^{Ord_ma\times (p-1)+r}-1)\)

\(m|a^{Ord_ma\times (p-1)+r}-1\)

\(a^{Ord_ma\times (p-1)+r}\equiv1(\bmod m)\Rightarrow a^r\equiv1(\bmod m)\Rightarrow r=0\)

必要性:设\(x=Ord_ma\times p\)

\(a^x\equiv a^{Ord_ma\times p}\equiv1(\bmod m)\)

推论:\(Ord_ma|\phi(m)\),显然

\(Quality2:若a\equiv b(\bmod m),则Ord_ma=Ord_mb\)

\(m|b-a\)设\(km=b-a,b=km+a\)

\((km+a)^{Ord_mb}\equiv1(\bmod m)\)

考虑展开二项式\(\Rightarrow a^{Ord_mb}\equiv1(\bmod m)\Rightarrow Ord_ma|Ord_mb\)

同理\(Ord_mb|Ord_ma\),合并即\(Ord_ma=Ord_mb\)

\(Quality3:a^p\equiv a^q(\bmod m)的充要条件是p\equiv q(\bmod Ord_ma)\)

充分性:\(a^{Ord_ma}\equiv1(\bmod m)\)

设\(p=Ord_ma\times k_p+r_p,q=Ord_ma\times k_q+r_q\)

\(a^{r_p}\equiv a^{r_q}(\bmod m)\)

\(r_p,r_q<Ord_ma\),根据\(Ord\)的定义\(r_p=r_q\)

必要性:\(a^{p}\equiv a^{p\bmod Ord_ma}\equiv a^{q\bmod Ord_ma}\equiv a^{q}\)

\(Quality4:a^0,a^1,a^2...a^{Ord_ma-1}\)构成一个关于\(m\)的剩余系

\(即证\forall i,j< Ord_ma,a^i\not\equiv a^j(\bmod m)\)

反证法

考虑\(\exists i<j< Ord_ma,a^i\equiv a^j(\bmod m)\)

\(m|a^j-a^i\Rightarrow m|a^i(a^{j-i}-1)\)

\(\gcd(a,m)=1\Rightarrow m|(a^{j-i}-1)\Rightarrow a^{j-i}\equiv1(\bmod m)\)

\(j-i<Ord_ma\),与\(Ord\)定义不符

\(Quality5:Ord_ma=Ord_m{a^{-1}}\)

\((aa^{-1})^{Ord_ma}\equiv (a^{-1})^{Ord_ma}\Rightarrow Ord_m{-a}|Ord_ma\)

同理\(Ord_m{a}|Ord_m{-a}\Rightarrow Ord_m{a}=Ord_m{-a}\)

\(Quality6:设x=Ord_ma,则Ord_ma^t=\dfrac{x}{gcd(x,t)}\)

设\(k=Ord_ma^t\),\(a^{kt}\equiv1(\bmod m)\)

\(a^x\equiv1(\bmod m),x|kt\)

即最小的\(k\),使得\(x|kt\),\(k=\dfrac{x}{gcd(x,t)}\)

\(Quality7:若w|m,则Ord_wa|Ord_ma\)

\(a^{Ord_ma}\equiv1(\bmod m)\)

\(a^{Ord_ma}=km+1=kdw+1\)

\(a^{Ord_ma}\equiv 1(\bmod w)\Rightarrow Ord_wa|Ord_ma\)

\(Quality8:若m\perp n,a\perp n,m\perp n,Ord_{nm}a=lcm(Ord_ma,Ord_na)\)