数论基础
基本运算
取模(mod)取余(rem)
定义
- 给定一个正整数p，任意一个整数n，一定存在等式 ：
- n = kp + r ；
- 其中 k、r 是整数，且 0 ≤ r < p，则称 k 为 n 除以 p 的商，r 为 n 除以 p 的余数。
- 对于正整数 p 和整数 a,b，定义如下运算：
- 取模运算：a % p（或a mod p），表示a除以p的余数。
- 模p加法： a+b算术和除以p的余数。(a + b) % p = (a % p + b % p) % p
- 模p减法： a-b算术差除以p的余数。(a - b) % p = (a % p - b % p) % p
- 模p乘法： a*b算术乘法除以p的余数。(a * b) % p = (a % p * b % p) % p
由以上定义易证欧几里得算法的正确性
- 定义(n,p)为n和p的最大公约数，要证明欧几里得算法正确性即证明(n,p)=(p,r);
- 设n,p的公因数为g,则g|n且g|p,由n = kp + r 得到g|r('|'为整除);
- 则n和p的最大公约数也是p和r的最大公约数.
取模和取余的区别
对于整型数a，b来说，取模运算或者取余运算的方法都是：
- 求 整数商： c = a/b;
- 计算模或者余数： r = a - c*b.
求模运算和求余运算在第一步不同: 取余运算在取c的值时，向0 方向舍入,而取模运算在计算c的值时，向负无穷方向舍入。
例如：
- 10 mod(-4)=-3
- 10 rem(-4)=-2
归纳：
- 当a和b符号一致时，求模运算和求余运算所得的c的值一致，因此结果一致。
- 当符号不一致时，结果不一样。求模运算结果的符号和b一致，求余运算结果的符号和a一致。
整除
若a除以b(b不等于0,a、b都为整数)，商为整数且余数为0，则叫做a能被b整除或者b能整除a，记作b|a
整除的基本性质
<blockquote>
①若a|b，a|c，则a|(b±c)。</br>
②若a|b，则对任意c(c≠0)，a|bc。</br>
③对任意非零整数a，±a|a=±1。</br>
④若a|b，b|a，则|a|=|b|。</br>
⑤如果a能被b整除，c是任意整数，那么积ac也能被b整除。</br>
⑥如果a同时被b与c整除，并且b与c互质，那么a一定能被积bc整除，反过来也成立。a|bc,(a,b)=1 => a|c
</br>
对任意整数a，b，b>0，存在唯一的数对q，r，使a=bq+r，其中0≤r< b，这个事实称为带余除法定理，是整除理论的基础。</br>
若c|a，c|b，则称c是a，b的公因数。若d是a，b的公因数，d≥0，且d可被a，b的任意公因数整除，则d是a，b的最大公因数。若a，b的最大公因数等于1，则称a，b互素，也称互质。累次利用带余除法可以求出a，b的最大公因数，这种方法常称为辗转相除法。又称欧几里得算法。</br>
</blockquote>
同余
设m是大于1的正整数，a、b是整数,如果(a-b)|m，则称a与b关于模m同余,记作a≡b(mod m),读作a与b对模m同余.
性质
- 反身性 a≡a (mod m)
- 对称性 若a≡b(mod m)，则b≡a (mod m)
- 传递性 若a≡b (mod m)，b≡c (mod m)，则a≡c (mod m)
- 同余式相加 若a≡b (mod m)，c≡d(mod m)，则a±c≡b±d (mod m)
- 同余式相乘 若a≡b (mod m)，c≡d(mod m)，则ac≡bd (mod m)
最大公约数(gcd 即 Greatest Common Divisor)
最大公因数，也称最大公约数、最大公因子，指两个或多个整数共有约数中最大的一个。
性质
记gcd=gcd(a,b)
- a=mgcd(a,b)，b=ngcd(a,b)，则(m,n)=1，即m和n互素
- gcd一定可以表示为a和b的线性组合，即ax+by=gcd
- gcd是a和b的线性组合所能表示出的最小正整数
gcd怎么求？
欧几里得算法(辗转相除法)
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
由性质2得出该方程一定有解，因此引入扩展欧几里得算法
- extend_gcd(a,b)表示求出ax+by=gcd(a,b)的一组解(x,y)
- 由a=(a/b)b+a%b得((a/b)b+a%b)x+by=gcd(a,b)即((a/b)x+y)b+x*(a%b)=gcd(b,a%b)=gcd(a,b)
- 设extend_gcd(b,a%b)求出的一组解为(x2,y2)
- x=y2,y=x2-(a/b)y2那么extend_gcd(a,b)的解可以用(y2,x2-(a/b)y2)表示
扩展欧几里得算法
int extend_gcd(int a,int b,int &x,int &y){
int d=a;
if(b!=0){
d=extend_gcd(b,a%b,y,x);
y-=(a/b)*x;
}
else{
x=1;
y=0;
}
return d;
}
由扩展欧几里得计算出的(x,y)不是方程ax+by=gcd(a,b)的唯一解，因为对任意整数k，令g=gcd(a,b)
- a(x+k(b/g))+b(y-k(a/g))=ax+by+kab/g-kab/g=g
- 即(x,y)如果为ax+by=g的一组解，那么(x+k(b/g),y-k(a/g))也是一组解。
- 用扩展欧几里得算法可以求出满足ax+by=gcd(a,b),x1≤x≤x2,y1≤y≤y2的所有解
最小公倍数
若有一个数X，可以被另外两个数A、B整除，且X大于（或等于）A和B，则X为A和B的公倍数。A和B的公倍数有无限个，而所有的公倍数中，最小的公倍数就叫做最小公倍数。两个整数公有的倍数称为它们的公倍数，其中最小的一个正整数称为它们两个的最小公倍数。同样地，若干个整数公有的倍数中最小的正整数称为它们的最小公倍数。记作lcm(A,B),其中lcm是英语中“最小公倍数”一词（lowest common multiple）的首字母缩写。
lcm(a,b)=a/gcd(a,b)*b
一元线性同余方程ax≡b(mod c)
- ax≡b(mod c)该方程有解，当且仅当b能被a与c的最大公约数整除，记作gcd(a,c)|b,记g=gcd(a,c)。
- 如果x为该方程的解，那么该方程所有的解可以表示为{x+k*c/g |k∈Z}
- 上述方程等价于ax+cy=b
- b%g!=0则方程无解 例如：3x≡2(mod 6) gcd(3,6)=3 3不整除2,方程无解。
- b%g=0时,用扩展欧几里得算法可以求出(x,y),使得ax+cy=g,则a(b/g)x+c(b/g)y=b,所以x=x(b/g)为该方程的一个解,进而可知原方程的所有解可以表示为{x+k(c/g) | k∈Z}。
- 求特殊解:由5可知,x=x*(b/g)是该方程的一个解,其他解都关于c/g与x同余，在模c下，共有c/g个解。
例如：
12x ≡ 20 (mod 28)中，g=gcd(12.28)=4,它的所有解为{4,11,18,28},关于7与x同余。记mod=c/g最小正整数解可以表示为 (x%mod+mod)%mod
Code
int linear(int a,int b,int c){
int x,y;
int g=extend_gcd(a,c,x,y);
if(b%g)
return -1;
x=x*(b/g);
int mod=c/g;
x=(x%mod+mod)%mod;
return x;
}
素数的筛选
- 素数：若一个大于1的整数除1和本身外无其他因子，则这个数是素数
- 合数：若一个大于1的整数不是素数，则其是合数
- 1既不是素数也不是合数
最经典的一种筛法-埃氏筛法(埃拉托斯特尼筛法)
核心思想：如果i是素数，那么对于所有的j≥2，i*j都不是素数
Code
int prime[maxn],res;
bool is_prime[maxn];
void get_prime(int n){
res=0;
memeset(is_prime,0,sizeof(is_prime));
is_prime[0]=is_prime[1]=1;
for(int i=2;i<=n;i++)
if(!is_prime[i]){
prime[res++]=i;
for(int j=2;j*i<=n;j++) is_prime[j*i]=1;
}
}
素因子分解
任意一个正整数都能分解成若干个素数乘积的形式
给定一个整数n,n可以表示为n=(p1a1)*(p2a2)......(pi^ai)的形式
pi为素数且互不相等。
Code
int fact[maxn][2],cnt;
void get_factor(int n){
cnt=0;
for(int i=2;i*i<=n;i++)
if(n%i==0){
fact[cnt][0]=i;
fact[cnt][1]=0;
while(n%i==0){
n/=i;
fact[cnt][1]++;
}
cnt++;
}
if(n>1) fact[cnt][0]=n,fact[cnt++][1]=1;
}
