基本運(yùn)算
取模(mod)取余(rem)
定義
- 給定一個正整數(shù)p译断，任意一個整數(shù)n谦炒，一定存在等式 ：
- n = kp + r 挫剑；
- 其中 k去扣、r 是整數(shù)，且 0 ≤ r < p樊破，則稱 k 為 n 除以 p 的商愉棱，r 為 n 除以 p 的余數(shù)唆铐。
- 對于正整數(shù) p 和整數(shù) a,b，定義如下運(yùn)算：
- 取模運(yùn)算：a % p（或a mod p）奔滑，表示a除以p的余數(shù)艾岂。
- 模p加法： a+b算術(shù)和除以p的余數(shù)。(a + b) % p = (a % p + b % p) % p
- 模p減法： a-b算術(shù)差除以p的余數(shù)朋其。(a - b) % p = (a % p - b % p) % p
- 模p乘法： a*b算術(shù)乘法除以p的余數(shù)王浴。(a * b) % p = (a % p * b % p) % p
由以上定義易證歐幾里得算法的正確性
- 定義(n,p)為n和p的最大公約數(shù)，要證明歐幾里得算法正確性即證明(n,p)=(p,r);
- 設(shè)n,p的公因數(shù)為g,則g|n且g|p,由n = kp + r 得到g|r('|'為整除);
- 則n和p的最大公約數(shù)也是p和r的最大公約數(shù).
取模和取余的區(qū)別
對于整型數(shù)a令宿，b來說叼耙，取模運(yùn)算或者取余運(yùn)算的方法都是：
- 求 整數(shù)商： c = a/b;
- 計(jì)算模或者余數(shù)： r = a - c*b.
求模運(yùn)算和求余運(yùn)算在第一步不同: 取余運(yùn)算在取c的值時粒没，向0 方向舍入,而取模運(yùn)算在計(jì)算c的值時筛婉，向負(fù)無窮方向舍入。
例如：
- 10 mod(-4)=-3
- 10 rem(-4)=-2
歸納：
- 當(dāng)a和b符號一致時癞松，求模運(yùn)算和求余運(yùn)算所得的c的值一致爽撒，因此結(jié)果一致。
- 當(dāng)符號不一致時响蓉，結(jié)果不一樣硕勿。求模運(yùn)算結(jié)果的符號和b一致，求余運(yùn)算結(jié)果的符號和a一致枫甲。
整除
若a除以b(b不等于0,a源武、b都為整數(shù))，商為整數(shù)且余數(shù)為0想幻，則叫做a能被b整除或者b能整除a粱栖，記作b|a
整除的基本性質(zhì)
<blockquote>
①若a|b，a|c脏毯，則a|(b±c)闹究。</br>
②若a|b，則對任意c(c≠0)食店，a|bc渣淤。</br>
③對任意非零整數(shù)a，±a|a=±1吉嫩。</br>
④若a|b价认，b|a，則|a|=|b|自娩。</br>
⑤如果a能被b整除用踩，c是任意整數(shù)，那么積ac也能被b整除。</br>
⑥如果a同時被b與c整除捶箱，并且b與c互質(zhì)，那么a一定能被積bc整除动漾，反過來也成立丁屎。a|bc,(a,b)=1 => a|c
</br>
對任意整數(shù)a，b旱眯，b>0晨川，存在唯一的數(shù)對q，r删豺，使a=bq+r共虑，其中0≤r< b，這個事實(shí)稱為帶余除法定理呀页，是整除理論的基礎(chǔ)妈拌。</br>
若c|a，c|b蓬蝶，則稱c是a尘分，b的公因數(shù)。若d是a丸氛，b的公因數(shù)培愁，d≥0，且d可被a缓窜，b的任意公因數(shù)整除定续，則d是a，b的最大公因數(shù)禾锤。若a私股，b的最大公因數(shù)等于1，則稱a时肿，b互素庇茫，也稱互質(zhì)。累次利用帶余除法可以求出a螃成，b的最大公因數(shù)旦签，這種方法常稱為輾轉(zhuǎn)相除法。又稱歐幾里得算法寸宏。</br>
</blockquote>
同余
設(shè)m是大于1的正整數(shù)宁炫，a、b是整數(shù),如果(a-b)|m，則稱a與b關(guān)于模m同余,記作a≡b(mod m),讀作a與b對模m同余.
性質(zhì)
- 反身性 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)
最大公約數(shù)(gcd 即 Greatest Common Divisor)
最大公因數(shù)歉备，也稱最大公約數(shù)、最大公因子匪燕，指兩個或多個整數(shù)共有約數(shù)中最大的一個蕾羊。
性質(zhì)
記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的線性組合所能表示出的最小正整數(shù)
gcd怎么求尼变？
歐幾里得算法(輾轉(zhuǎn)相除法)
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
由性質(zhì)2得出該方程一定有解利凑，因此引入擴(kuò)展歐幾里得算法
- 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)
- 設(shè)extend_gcd(b,a%b)求出的一組解為(x2,y2)
- x=y2,y=x2-(a/b)y2那么extend_gcd(a,b)的解可以用(y2,x2-(a/b)y2)表示
擴(kuò)展歐幾里得算法
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;
}
由擴(kuò)展歐幾里得計(jì)算出的(x,y)不是方程ax+by=gcd(a,b)的唯一解，因?yàn)閷θ我庹麛?shù)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))也是一組解。
- 用擴(kuò)展歐幾里得算法可以求出滿足ax+by=gcd(a,b),x1≤x≤x2,y1≤y≤y2的所有解
最小公倍數(shù)
若有一個數(shù)X蛉威，可以被另外兩個數(shù)A日丹、B整除，且X大于（或等于）A和B蚯嫌，則X為A和B的公倍數(shù)哲虾。A和B的公倍數(shù)有無限個，而所有的公倍數(shù)中择示，最小的公倍數(shù)就叫做最小公倍數(shù)束凑。兩個整數(shù)公有的倍數(shù)稱為它們的公倍數(shù)，其中最小的一個正整數(shù)稱為它們兩個的最小公倍數(shù)栅盲。同樣地汪诉，若干個整數(shù)公有的倍數(shù)中最小的正整數(shù)稱為它們的最小公倍數(shù)。記作lcm(A,B),其中l(wèi)cm是英語中“最小公倍數(shù)”一詞（lowest common multiple）的首字母縮寫谈秫。
lcm(a,b)=a/gcd(a,b)*b
一元線性同余方程ax≡b(mod c)
- ax≡b(mod c)該方程有解扒寄，當(dāng)且僅當(dāng)b能被a與c的最大公約數(shù)整除，記作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時,用擴(kuò)展歐幾里得算法可以求出(x,y),使得ax+cy=g,則a(b/g)x+c(b/g)y=b,所以x=x(b/g)為該方程的一個解,進(jìn)而可知原方程的所有解可以表示為{x+k(c/g) | k∈Z}硕淑。
- 求特殊解:由5可知,x=x*(b/g)是該方程的一個解,其他解都關(guān)于c/g與x同余课竣，在模c下嘉赎，共有c/g個解。
例如：
12x ≡ 20 (mod 28)中于樟，g=gcd(12.28)=4,它的所有解為{4,11,18,28},關(guān)于7與x同余公条。記mod=c/g最小正整數(shù)解可以表示為 (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;
}
素?cái)?shù)的篩選
- 素?cái)?shù)：若一個大于1的整數(shù)除1和本身外無其他因子，則這個數(shù)是素?cái)?shù)
- 合數(shù)：若一個大于1的整數(shù)不是素?cái)?shù)迂曲，則其是合數(shù)
- 1既不是素?cái)?shù)也不是合數(shù)
最經(jīng)典的一種篩法-埃氏篩法(埃拉托斯特尼篩法)
核心思想：如果i是素?cái)?shù)赃份，那么對于所有的j≥2，i*j都不是素?cái)?shù)
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;
}
}
素因子分解
任意一個正整數(shù)都能分解成若干個素?cái)?shù)乘積的形式
給定一個整數(shù)n,n可以表示為n=(p1a1)*(p2a2)......(pi^ai)的形式
pi為素?cái)?shù)且互不相等奢米。
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;
}
