组合数学(1)数论

ACM暑期集训 组合数学（1） 数论

1 约数和倍数

设 a，b为整数，a≠0.

若有一整数c，使得 b = ac，则称 a是b的因数 或称a是b的约数 称b为是a的倍数

并称a整除b，记为a|b

整数的整除性有下列基本性质： ① 1|a ② a|0 ③ a|a

④ 若a|b且b|c，则a|c.

⑤ 若a|b，则对任意整数m，有am|bm ⑥ 若ac|bc且c≠0，则a|b

⑦ 若a|b且a|c，有 a|(b+c) 整数的表示法：

带余形式 b=aq+r 0≤r<|a|

十进制表示形式 b?ann?1n10?an?110????a0

标准分解式 b?pa1aan1p22??pn 2的乘方与奇数之积式 b?2mt(t为奇数)

2 最大公约数和最小公倍数 最大公约数GCD(a,b)

若GCD(a,b)=1，称a与b互素。 最小公倍数LCM(a,b)

ab = GCD(a,b)×LCM(a,b)

辗转相除法（Euclid算法）

如果m除以n的商是q，余数是r，即 m=nq+r，则 GCD(m,n)=GCD(n,r) int gcd(int a,int b) int GCD(int a,int b) { {

return (b? gcd(b,a%b):a); if(b==0) return a; } return GCD(b,a%b); int gcd(int a,int b) //非递归实现 } { while(b){int t=a%b;a=b;b=t;} return a;

} 如果除法的开销很大，有一种二进制算法可以只用减法、移位和判奇偶。

gcd(a,a)=a, 当a>b时，分情况讨论：

a和b均为偶数，gcd(a,b)=2*gcd(a/2,b/2) a为偶数b为奇数，gcd(a,b)=gcd(a/2,b) a和b均为奇数，gcd(a,b)=gcd(a-b,b) int gcd(int a,int b) {

int t=1,c,d; while(a!=b) {

if(a

if(!(a&1)){a>>=1;c=1;} else c=0; if(!(b&1)){b>>=1;d=1;} else d=0; if(c&&d) t<<=1;

else if(!c&&!d) a -= b; }

return t*a; }

gcd(a,b)是集合{ax+by} x∈Z,y∈Z中的最小正整数。

线性不定方程ax+by=c

给出整数a, b, c，先求出一组解，然后讨论如何表示通解（所有解）。 设gcd(a,b)=d。如果c不是d的倍数，那么方程无解。

在有解的情况，设c=c0*d，则可以先求出ax+by= d的一组解(x0,y0) 则ax0+by0=d，两边乘以c0得：a(c0*x0)+b(c0*y0)=c 因此(c0*x0,c0*y0)是原方程的一组解。

所以，核心问题是：求ax+by=gcd(a,b)的解。 下面的扩展Euclid算法求出了这样一组解。

void gcd(int a,int b,int &d,int &x,int &y) {

if(!b){d=a; x=1; y=0;} else {

gcd(b,a%b,d,y,x); y -= x*(a/b); } }

求出一组特解(x0,y0)，通解为(x0+k*b0,y0-k*a0) 其中k取任意整数。a0=a/gcd(a,b),b0=b/gcd(a,b) 3 素数和合数

一个大于1且只能被1和它本身整除的整数，称为素数；否则称为合数。

小于100的素数有25个，即2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97。 若正整数b有一因数a，而a又是素数，则称 a为b的素因数。 例：12=3×4，3是12的素因数，而4不是

若a是大于1的整数，则a的大于1的最小因数一定是素数。

公元前三世纪，古希腊数学家欧几里德Euclid证明了素数有无穷多个。 设 p1，p2，… ，pn 是互不相同的素数，则 a=p1p2…pn+1 是新的素数。 合数a必有一素因数小于或等于a

与素数相关的常见问题：

（1）求[1,n]之间的所有素数（筛选法） （2）求[a,b]之间的素数个数 （3）判断一个数n是否为素数 （4）互素问题

bool isPrime (int p) {

for(int i=2;i*i<=p;i++) if(p%i==0) return false; return true; }

如果p不是素数，那么它一定有一个素因子。注意到偶数中只有2是素数，而且除了3之外所有素数除以6的余数均为1或5，因此可以从5开始，交替以2、4为步长增加i。由于计算

p时间比较长，而每次计算i*i时间也是一种浪费，

可以利用(i+1)2=i2+2i+1进行递推。变量j即是保存i2的值，k是步长。代码如下：

bool isPrime (int p) {

if(p==2||p==3) return true;

else if(p%2==0||p%3==0) return false ; for(i=5,j=25,k=4;j<=p;i+=(k=6-k),j=i+i-1)

if(p%i==0) return false ; return true ; }

4 算术基本定理

每个正整数都可以惟一地表示成素因子的乘积，其中素因子从小到大依次出现。 （这里的乘积可以有0个、1个或多个素因子）

换句话说，任意正整数n可以写成n?2a13a25a3?pak （如360=23325） 则n的正约数个数为：d(n)=(a1+1)(a2+1)(a3+1)…(ak+1)

如：28=227，则28的正约数个数为(2+1)(1+1)=6 分别为：1, 2, 4, 7, 14, 28

5 模(mod)运算

同余：a≡b(mod n)

表示(a mod n) = (b mod n),即a和b除以n有相同的余数。 表示形式：a=x*n+r;b=y*n+r; 相减得：(a-b)=(x-y)*n

结论：a≡b(mod n)等价于它们的差能被 n整除，即n|(a-b)。

模n等价类

根据模n的余数把所有整数划分成n个等价类。 包含整数a的等价类为：[a]n={a+kn}

如[3]7={...,-11,-4,3,10,17,...}，也可以表示为[-4]7或者[10]7 如果两个整数a和b属于同一个等价类，即a和b关于模n同余。

所有等价类的集合记为Zn={[a]n:0≤a≤n-1}，简记为Zn={0,1,...,n-1} Zn的每个元素是一个等价类而不是一个数。

当考虑[-1]n时要能立刻明白它实际上也是[n-1]n a关于模n的逆的求法

ax≡1(mod n)的解x称为a关于模n的逆。设ax-1=ny，即ax-ny=1 当且仅当a和n互素时，方程ax-ny=1有解。如果逆存在，一定是唯一的。 int mod(int x,int n){return (x%n+n)%n;} int inv(int a,int n) {

int d,x,y;

gcd(a,n,d,x,y);

return (d==1 ? mod(x,n):-1); }

单变元的模线性方程ax≡b(mod n)

存在y使得ax-b=ny，移项得ax-ny=b，是一个标准的线性不定方程。

模方程虽然解有无穷多组，但是剩余系解是有限的。如果x=1是解，那么显然x=n+1也是解。由于1和n+1属于同一个剩余系，因此它们是同一组解。一般情况下，只考虑0~n-1之间的解。

设gcd(a,n)=d，则b不是d的倍数时无解，否则两边同时除以d，得到： a0*x-n0*y=b0，即a0x≡b0(mod n0)

由于a0和n0互素，因此只需要左乘a0-1，则解为x≡(a0)-1b0(mod n0) 需要还原为模n的剩余系。还原的方法也很简单：一共有d个解。显然第一个解为(a0)-1b0，以后每个解等于前一个解加上n0，即n/d。代码如下： void linear_mod_equation (int a,int b,int n,int sol[]) {

gcd(a,n,d,x,y);

if(b%d) d=0; // no solution else {

sol[0]=x * (b/d)%n; // first solution for(int i=1;i

sol[i]=(sol[i-1]+n/d)%n; } }

中国剩余定理

下面考虑模线性方程组的情形。

由于ax≡b(mod n)有解时可以转化成x≡x0(mod n0)（x0=(a0)-1b0） 因此方程组转化成多个形如x≡x0(mod m) 的方程联立构成的方程组。 在解方程前，还可以继续把方程进行变形。 如果a和b互素，则x≡x0(mod ab)可以拆为x≡x0(mod a)和x≡x0(mod b)。 因此所有方程都可以变为模为素数的幂的形式。 即只需考虑所有m两两互素的情况。

令M为所有m的乘积，wi=M/mi，则(wi,mi)=1 因此存在pi和qi使得wipi+miqi=1成立。

令ei=wipi。等式两边模mi可知ei mod mi = 1。

可以验证e1a1 +e2a2 +……+enan是问题的解，因为它对mi取模时，所有其他ej模都等于0（因为wj包含因子mi），而ei的模为1。代码如下：

int china(int n,int a[],int m[]) {

int M=1,dummy;

for(int i=0;i

w=M/m[i];

gcd(m[i],w,dummy,dummy,y);

x=(x+y*w*a[i])%M; // accumulate e*的和a }

return (n+x%M)%M; // adjust to [0,M-1] }

模取幂运算之反复平方法

ab mod n (a,b,n都是正整数)

ab呈指数增长，因此很易超出计算机表示范围，我们引出一个能计算ab mod n的值的有用算法－反复平方法（Head算法），即： ab mod n =

(…((((a mod n) * a) mod n) * a) mod n) * a) mod n… * a)mod n; 由此引出迭代式： d=a;

for(i=2;i<=b;i++) d=(d%n)*a; d=d%n;

常用等式与定理

1+3+5+...+(2n-1)=n^2

1*2+2*3+3*4+...+n*(n+1)=n*(n+1)*(n+2)/3 1*1!+2*2!+3*3!+...+n*n!=(n+1)!-1

1^2+2^2+3^2+...+n^2=n*(n+1)*(2n+1)/6

1^2-2^2+3^2-...+(-1)^n*n^2=(-1)^(n+1)*n*(n+1)/2

2^2+4^2+...+(2n)^2=2n*(n+1)*(2n+1)/3 1/2!+2/3!+...+n/(n+1)!=1-1/(n+1)! 2^(n+1)<1+(n+1)2^n

1^3+2^3+3^3+...+n^3=(n*(n+1)/2)^2

1/(2^2-1)+..+1/((n+1)^2-1)=3/4-1/(2*(n+1))-1/(2*(n+2)) 1/2n<=1*3*5*...*(2n-1)/(2*4*6*...*2n)<=1/sqrt(n+1) 2^n>=n^2,n=4,5,... 2^n>=2n+1,n=3,4,...

r^0+r^1+...+r^n<1/(1-r),n>=0,0

1*r^1+2*r^2+...+n*r^n=1,0=1

(a(1)*a(2)*...*a(2^n))^(1/2^n)<=(a(1)+a(2)+...+a(2^n))/2^na(i)是正数

cos(x)+...+cos(nx)=cos((x/2)*(n+1))*sin(nx/2)/sin(x/2)

1*sin(x)+2*sin(2x)+...+n*sin(nx)=

sin((n+1)*x)/(4*sin(x/2)^2)-(n+1)cos((2n+1)/2*x)/(2*sin(x/2))

5^n-1能被4整除 7^n-1能被6整除 11^n-6能被5整除

6*7^n-2*3^n能被4整除 3^n+7^n-2能被8整除

定义H(k)=1+1/2+1/3+...+1/k 则

1+n/2<=H(2^n)<=1+n

H(1)+H(2)+...+H(n)=(n+1)*H(n)-n

1*H(1)+2*H(2)+...+n*H(n)=n*(n+1)/2*H(n+1)-n*(n+1)/4

本文来源：https://www.bwwdw.com/article/97pr.html