基础数论复习笔记

前言

复习笔记第7篇。注意,由于数论的特殊性,主要以放板子和各种结论性质算法整理为主,不再以题目为导向。

感觉这篇写得好烂,快要变成板子集合了qaq

1. 质数

Eratosthenes 筛法(埃式筛)

思想是标记每个质数的倍数。

void get_primes( int n )
{
        memset( vis,0,sizeof(vis) );
        for ( int i=2; i<=n; i++ )
        {
                if ( vis[i] ) continue;
            /*save the prime,or print*/
                for ( int j=i; j<=n/i; j++ ) vis[i*j]=1;
        }
}

线性筛

令 \(vis[i]=i,(i\in prime)\) ,然后扫描 \(i\) 之前的每一个质数 \(p\) ,\(vis[i\times p]=p\) (用最小的质因子标记合数)

void get_prime( int n )
{
        memset( vis,0,sizeof(vis) ); cnt=0; 
        for ( int i=2; i<=n; i++ )
        {
                if ( !vis[i] ) prime[++cnt]=i; 
                for ( int j=1; j<=cnt && prime[j]*i<=N-1; j++ )
                {
                        vis[prime[j]*i]=1;
                        if ( i%prime[j]==0 ) break;
                }
        }
}

2. 约数

算数基本定理推论

令 \(N\) 的唯一分解写为:\(N=p_1^{c_1}p_2^{c_2}p_3^{c_3}\dots p_m^{c_m}\)

约数个数为: \(\prod _{i=1}^m (c_i+1)\) (考虑其组合意义)

约数和为: \(\prod _{i=1}^m(\sum_{j=0}^{c_i} (p_i)^j)\)

求单个数的约数,试除即可,\(O(\sqrt n)\) ,注意判平方。

求 \(1\sim N\) 的约数:i=1 to n, j=1 to (n/i), a[i*j].push_back(i)

gcd

int gcd( int a,int b ) { return b ? gcd( b,a%b ) : a; }

欧拉函数

\(1\sim N\) 中与 \(N\) 互质的个数,记为 \(\varphi(N)\)

\(\varphi(N)=N\times \prod _{p\in prime,p|N}(1-\frac{1}{p})\) (容斥可以得到)

互质的数之和为 : \(\varphi(n)\times n/2\) (考虑平均数)

线性筛改造的欧拉函数筛

原理: \(p|x,\varphi(x\times p)=\varphi(x)\times p;\) 否则,\(\varphi(x\times p)=\varphi(x)\times(p-1)\) ,注意质数和1的特判。

phi[1]=1;
for ( int i=2; i<N; i++ )
{
    	if ( !f[i] ) phi[prime[++cnt]=i]=i-1;
    	for ( int j=1; j<=cnt && (k=i*prime[j])<N; j++ )
        {
            	f[k]=1;
            	if ( i%prime[j] ) phi[k]=phi[i]*(prime[j]-1);
            	else { phi[k]=phi[i]*prime[j]; break; }
        }
}

3 同余

费马小定理

\(p\in prime,=> \forall a\in Z,a^p\equiv a(\bmod p)\) (可以用于求模数为质数的单个逆元)

欧拉定理

\(a,n\in Z^+,\gcd(a,n)=1,=> a^{\varphi(n)}\equiv1 (\bmod n)\)

推论

\(a,n\in Z^+,\gcd (a,n)=1,b\in Z^+,=> a^b\equiv a^{b\mod \varphi(n)}(\bmod n)\)

裴蜀定理

\(\forall a,b\in Z,\exists x,y\in Z ,ax+by=\gcd(a,b)\)

exgcd

link 求解不定方程 \(ax+by=c\) (特解)

当 \(b=0\) 时,\(\gcd(a,b)=a,\) 有解 \(x=1,y=0\)

当 \(b\neq 0\) 时,递归求解 \(exgcd(b,a\%b,x,y)\) ,设 \(a'=b,b'=a\bmod b\) ,可以得到 \(a'x'+b'y'=\gcd(a,b)\) 的特解,也就是 \(bx'+(a\%b)y'\) .变形得到 \(ay'+b(x'-a/b)y'\) ,所以原来的解就是 \(x=y',y=b(x'-a/b*y')\)

int exgcd( int a,int b,int &x,int &y )		//最终返回的是a,b的gcd
{
    if ( b==0 ) { x=1; y=0; return a; }
    int d=exgcd( b,a%b,y,x ); y-=a/b*x;
    return d;
}

乘法逆元

  1. 当模数 \(p\in prime\) ,直接费马小定理 \(a^{-1}=a^{p-2}\bmod p\)

  2. 只保证 \(a,p\) 互质,那么可以求解 \(a\times x\equiv 1(\bmod p)\) 。有解当且仅当 \(\gcd(a,p)=1\) ,可以改写为 \(ax+py=1\) ,用 exgcd 求出一个特解,然后通过加减模数得到正整数解即可。

  3. 线性求 \(1\sim n\) 逆元:

推式子。首先,显然有 \(1^{-1}=1(\bmod p)\)

然后设 \(p=ki+r\) ,

\[ki+r\equiv 0(\bmod p)\\\\ k\times r^{-1}+i^{-1}\equiv 0(\bmod p)\\\\ i^{-1}\equiv -k\times r^{-1}(\bmod p)\\\\ i^{-1}\equiv -\lfloor\frac{p}{i}\rfloor \times (p\bmod i)^{-1}(\bmod p) \]

通过前面的项可以得到。

 inv[1]=1; 
for ( int i=2; i<=n; i++ )
        inv[i]=(ll)(p-p/i)*inv[p%i]%p;
  1. 求阶乘逆元(一般用于算组合数,需要模数为质数)

    先费马小定理求出 \(inv[n]=fac[n]^{-1}\) (\(fac[i]\) 表示 \(i!\) ),然后 \(inv[i]=inv[i+1]\times (i+1)\) (考虑逆元的意义),判边界即可。

扩展中国剩余定理(exCRT)——同余方程组

(由于中国剩余定理需要模数两两互质,太过鸡肋 ,所以直接上ex了)

众所周知,CRT和exCRT一点关系都没有……原理见 这篇题解

exCRT解决的问题:求形如 \(x\equiv a_i(\bmod b_i)\) 的方程组的最小正整数解。

考虑递推。假设前 \(k-1\) 个方程的最小正整数解是 \(ans_{k-1}\) ,令 \(M=\gcd(b_1,b_2,...,b_{k-1})\)

设 \(ans_k=ans_{k-1}+x\times M\) ,那么根据方程,有 \(ans_{k-1}+xM\equiv a_k(\bmod b_k)\)

\(\therefore Mx\equiv a_k-ans_{k-1}(\bmod b_k)\) ,用未知系数 \(y\) 去掉取模得 \(Mx+b_ky=a_k-ans_{k-1}\) ,然后 exgcd 即可。判无解的话就是裴蜀定理。

码源:POJ 2891 ,洛谷模板最后一个点由于爆 long long 了没过。

ll exgcd( ll a, ll b, ll &x, ll &y )
{
        if ( b==0 ) { x=1,y=0; return a; }
        ll d=exgcd( b,a%b,y,x ); y-=a/b*x;
        return d;
}

ll inline mod( ll a,ll b )
{
        return ((a % b)+b)%b;
}

int main()
{
        scanf( "%d",&n );
        ll a1,m1; scanf( "%lld%lld",&a1,&m1 );
        for ( int i=1; i<n; i++ )
        {
                ll a2,m2,k1,k2; scanf( "%lld%lld",&a2,&m2 );
                ll d=exgcd( a1,-a2,k1,k2 );
                if ( (m2-m1)%d )
                { printf( "-1\n" ); return 0;  }
                k1=mod( k1*(m2-m1)/d,abs( a2/d ) );
                m1=k1*a1+m1; a1=abs( a1/d*a2 );
        }
        printf( "%lld\n",m1 );

        return 0;
}

BSGS及其扩展——高次同余方程

解决问题:\(A^x\equiv B(\bmod p)\) 的最小自然数解。

首先是 BSGS ,保证 \(p\in prime.\) 那么可以用费马小定理,\(x\) 在模 \(p-1\) 意义下产生循环,范围缩小至 \([1,p-1]\)

考虑分块。令 \(t=\lceil \sqrt p\rceil ,x=i\times t-j,0\leq j\leq t-1\) (写成减法是为了避免求逆元)

当 \(i=0\) 时,显然只有 \(\sqrt p\) 个 \(x\) ,暴力枚举,建立 Hash表(后面有用),\(H(T)\) 表示是否存在一个 \(x\) 使得 \(A^b\equiv T\)

当 \(i>0\) 时, 原式等价于

\[A^{i\times t-j}\equiv B\bmod p\\\\ (A^t)^i/A^j\equiv B\bmod p\\\\ (A^t)^i\equiv B\times A^j\bmod p \]

由于记录了结果,直接 map 就好了。 题源link

scanf( "%d%d%d",&p,&x,&y );
int m=sqrt(p)+1,s=y;
for ( int i=0; i<m; i++ )
		M[s]=i,s=1ll*s*x%p;
int pow=power( x,m ); s=1;
for ( int i=1; i<=m; i++ )
{
		s=1ll*s*pow%p;
		if ( M.count(s) )  { printf( "%d\n",i*m-M[s] ); return 0; }
}
printf( "no solution" );

然后是 exBSGS 。和很多ex一样,模数不是质数了。

首先考虑无解。当 \(B\neq 1\) 且 \((A,p)\nmid B\) 的时候无解。

然后考虑如何求解。设 \(G=(A,p)\) ,两边同除以 \(G\) 得

\[A^{x-1}\frac{A}{G}\equiv \frac{B}{G}\bmod \frac{p}{G} \]

设 \(g=(\frac{A}{G})^{-1}\) 。式子两边同乘 \(g\) ,根据逆元定义得:

\[A^{x-1}=\frac{B}{G}\times g\bmod \frac{p}{G} \]

令 \(x'=x-1,B'=\frac{B}{G}\times g,p'=\frac{p}{G}\) ,得到

\[A^{x'}\equiv B'(\bmod p') \]

于是不断递归,直到出现质数时 BSGS 即可。题源link

void exBSGS( int x,int y )
{
		if ( y==1 ) { printf( "0\n" ); return; }
		int d=gcd( x,p ),k=1,t=0;
		while ( d^1 )
		{
				if ( y%d ) { printf( "No Solution\n" ); return; }
				t++; y/=d; p/=d; k=(x/d)*1ll*k%p;
				if ( y==k ) { printf( "%d\n",t ); return; }
				d=gcd( x,p );
		}
    //-----------------------------------------
		int s=y; M.clear(); int m=sqrt(p)+1;
		for ( int i=0; i<m; i++ )
				M[s]=i,s=1ll*s*x%p;
		s=k; k=power( x,m );
		for ( int i=1; i<=m; i++ )
		{
				s=1ll*s*k%p;
				if ( M[s] )  { printf( "%d\n",i*m-M[s]+t ); return; }
		}
		printf( "No Solution\n" );
}

Lucas和扩展Lucas——大组合数取模

又是一个原定理和扩展没有关系的典型案例

首先是卢卡斯定理原样:\(C_n^m\bmod p=C_{n/p}^{m/p}\times C_{n\bmod p}^{m\bmod p}\bmod p\) ,然而还是要模数为质数。

所以直接看扩展吧。

解决问题:\(C_n^m\bmod p,p\leq 1e6\)

设 \(p=p_1^{c_1}p_2^{c_2}...\) ,首先求出

\[C_n^m\bmod p_1^{c_1}\\\\ C_n^m\bmod p_2^{c_2}\\\\ \dots \]

然后用中国剩余定理合并即可。假设现在要求 \(C_n^m\bmod p^k=\dfrac{n!}{m!(n-m)!}\bmod p^k\) .

先将阶乘中 \(p\) 的倍数提取出来,共 \(\lfloor\frac{n}{p}\rfloor\) 个。这中间每一项都除以 \(p\) ,可以得到 \(\lfloor \dfrac{n}{p}\rfloor!\) ,递归求解。

对于剩下的几项,关于 \(p\) 存在循环节,且长度小于 \(p^k\) ,可以一起求解。最后多余的几项暴力即可。

为了达到除法的效果,考虑 \(p\) 的幂次的出现次数。设 \(f(n)\) 表示 \(n!\) 中 \(p\) 的因数个数,\(f(n)=f(\lfloor \dfrac{n}{p}\rfloor)+\lfloor \dfrac{n}{p}\rfloor,f(x)=0(x<p)\) .

//省略gcd,power(快速幂),exgcd
ll fac( ll n,ll pi,ll pk )
{
    	if ( !n ) return 1;
    	ll res=1;
    	for ( ll i=2; i<=pk; i++ )
        	if ( i%pi ) (res*=i)%=pk;
    	res=power( res,n/pk,pk );
    	for ( ll i=2; i<=n%pk; i++ )
        	if ( i%pi ) (res*=i)%=pk;
    	return res*fac(n/pi,pi,pk)%pk;
}

ll inv( ll n,ll mod )
{
    	ll x,y; exgcd( n,mod,x,y );
    	return (x+=mod)>mod ? x-mod : x;
}

ll CRT( ll b,ll mod )
{
    	return b*inv(p/mod,mod)%p*(p/mod)%p;
}

ll C( ll n,ll m,ll pi,ll pk )
{
    	ll up=fac( n,pi,pk ),t1=fac( m,pi,pk ),t2=fac( n-m,pi,pk ),k=0;
    	for ( ll i=n; i; i/=pi )  k+=i/pi;
    	for ( ll i=m; i; i/=pi ) k-=i/pi;
    	for ( ll i=n-m; i; i/=pi ) k-=i/pi;
    	return up*inv(t1,pk)%pk*inv(t2,pk)%pk*power(pi,k,pk)%pk;
}

ll exlucas( ll n,ll m )
{
    	ll res=0,tmp=p,pk;
    	int lim=sqrt(p)+5;
    	for ( int i=2; i<=lim; i++ )
        	if ( tmp%i==0 )
        	{
            	pk=1;
            	while ( tmp%i==0 ) pk*=i,tmp/=i;
            	res=(res+CRT(C(n,m,i,pk),pk))%p;
        	}
    	if ( tmp>1 ) res=(res+CRT(C(n,m,tmp,tmp),tmp))%p;
    	return res;
}

高斯消元——解线性方程组

解决问题:求解线性方程组。

具体步骤就是将每个方程的未知数系数放在左侧,常数在右侧,类似笔算消元的方法解,每次用一个 i 系数不为0的方程消其他方程的i。如果出现形为 d=0 的方程,无解;若一个未知数的系数全为0,那么值不能确定,属于*元。(以下代码中对无解的定义不同,根据题目)

for ( int i=1; i<=n; i++ )
{
		cnt=i;
		while ( a[cnt][i]==0 && cnt<=n ) cnt++;
		if ( cnt==n+1 ) { printf( "No Solution" ); return 0; }
		for ( int j=1; j<=n+1; j++ )
				swap( a[i][j],a[cnt][j] );			//找一行第 i 元不为0的方程,换到第 i 行
		double k=a[i][i];
		for ( int j=1; j<=n+1; j++ )			//计算消元的倍数
				a[i][j]/=k;
		for ( int j=1; j<=n; j++ )			//消元
				if ( i!=j )
				{
						double kt=a[j][i];
						for ( int m=1; m<=n+1; m++ )
								a[j][m]-=kt*a[i][m];
				}
}

线性基

见学习笔记

4 组合数学

二项式定理

\[(a+b)^n=\sum_{k=0}^n C_n^ka^kb^{n-k} \]

多重集排列数

\[\dfrac{n!}{n_1!n_2!\dots n_k!} \]

多重集组合数

\[C_{k+r-1}^{k-1} \]

卡特兰数列

\[Cat_n=\dfrac{C_{2n}^n}{n+1} \]

容斥

Orz gzy

莫比乌斯函数\((M\ddot{o}bius)\)

\[\mu(N)= \left\{ \begin{aligned} 0 & & \exist\ i\in[1,m],c_i>1 \\ 1 & & m\equiv 0(\bmod 2),\forall i\in[1,m],c_i=1 \\ -1 & & m\equiv 1(\bmod 2),\forall i\in[1,m],c_i=1 \\ \end{aligned} \right. \]

( \(c_i\) 的意义见唯一分解定理,也就是 \(N=p_1^{c_1}...\) )

埃式筛——莫比乌斯函数

for ( int i=1; i=n; i++ ) miu[i]=1,v[i]=0;
for ( int i=2; i<=n; i++ )
{
    	if ( v[i] ) continue;
    	miu[i]=-1;
    	for ( int j=2*i; j<=n; j+=i )
        {
            	v[j]=1;
            	if ( (j/i)%i==0 ) miu[j]=0;
            	else miu[j]*=-1;
        }
}

5 概率期望

期望的线性性质

\(E(aX+bY)=a\times E(x)+b\times E(Y)\)

练习题见 期望题选做 (目前都是提高内难度,保证没有任何反演之类的东西参与,是简单DP+期望)

6 0/1分数规划

模型

给定整数 \(a_1,a_2,\dots,a_n\) 和 \(b_1,b_2,\dots ,b_n\) ,求一组解 \(x_i(x_i\in \{0,1\})\) 使下式最大化:

\[\dfrac{\sum_{i=1}^na_i\times x_i}{\sum_{i=1}^nb_i\times x_i} \]

做法

二分答案,计算 \(\sum_{i=1}^n(a_i-mid\times b_i)\times x_i\) 的最大值。

大多与图论结合,如 POJ3621

7 博弈论,SG函数

NIM博弈

的先手必胜,当且仅当 \(A_1\oplus A_2\oplus \dots \oplus A_n\neq 0\)

SG函数

\(mex(S)=min\{x\}(x\in N,x\notin S)\)

在有向图游戏(无法移动判负,有向无环的状态图)中, 令 \(y_1,y_2,...,y_k\) 是 \(x\) 的后继节点

\[SG(x)=mex(\{SG(y_1),SG(y_2),...,SG(y_k)\}) \]

\(m\) 个游戏的和就是各个 \(SG\) 函数的 \(xor\) 和。

定理

某个局面必胜,当且仅当 \(SG>0\) ;

某个局面必败,当且仅当 \(SG=0\) .

Last

写得挺赶的,To be continued...

上一篇:「二次剩余」Tonelli - Shank's algorithm


下一篇:类欧几里得算法