裴屬定理{

a=mk,b=nk

(m,n)=1

xm+yn=1

}

乘法逆元：https://blog.csdn.net/weixin_43828245/article/details/102753727（好歹看的懂定義。。。

哦，還有https://blog.csdn.net/qq_43791377/article/details/89809193

{求法：費馬小定理

exgcd

遞推

}

埃式篩 https://blog.csdn.net/holly_Z_P_F/article/details/85063174（即按倍數(shù)篩（代碼中i*2可改為i*i)

線性篩（歐拉篩（歐拉我恨你）也是找到一個數(shù)然后篩它倍數(shù)，但是歐拉篩可以做到不重復(fù)https://blog.csdn.net/weixin_45691703/article/details/128569209

注意！：gcd為最大公約數(shù)，lcm為最小公倍數(shù)（很顯然，我腦子不太好使，記不住）。。。

{高精度適宜更相減損法{

gcd(a,b)=gcd(b,a-b)=gcd(a,a-b)

gcd(2a,2b)=2gcd(b,a mod b)

}

代碼更加簡單的歐幾里得算法{

gcd(a,b)=gcd(b,a mod b)

}

}

歐拉函數(shù)（歐拉我有恨你了）phi(m)就是中與互素的數(shù)的個數(shù)

n=pow(p1,c1)*pow(p2,c2)*...*pow(pm,cm)

則phi(n)=??(??) = N ? ?質(zhì)數(shù)p|N(1 ? 1/??)

歐拉函數(shù)性質(zhì)

? 1~N中與N互質(zhì)的數(shù)之和為N???(??)/2

?若a,b互質(zhì)，則??(????) = ??(a)??(b) （積性函數(shù)）

?若p|n且pow(p,2)|n，則?? ?? = ?? ??/?? ? ??

?若p|n且pow(??,2)? ??，則?? ?? = ?? ??/?? ? (?? ? 1)

? σ??|?? ?? ?? = ?? （狄利克雷卷積)

*積性函數(shù)

?如果當a,b互質(zhì)時，有f(????) = f(a)f(b)，則稱f為積性函數(shù)

?若f是積性函數(shù)，且N = ??1??1??2??2 … ????????，則f(N) = σ??=1 ?? ??(pici)

...

好吧我數(shù)學知識有限謝謝

同余里面一個數(shù)上面一個橫杠代表模m余這個數(shù)的同余類，0到m-1打橫杠就叫完全剩余系

在完全剩余系中互質(zhì)的即為簡化剩余系，簡化剩余系關(guān)于模m乘法封閉

歐拉的又雙叒叕定理等{

費馬小定理：pow(a,p) = a(mod p),即pow(a,p-1)=1(mod p)

歐拉定理：當(a,n)=1 ,pow(a,phi(n))=1(mod n)

當p是質(zhì)數(shù)時，phi(p)=p-1,pow(a,p)=(這個是等號)pow(a,phi(p)+1)=a(mod p)

推論：若(a,n)=1,對于任意正整數(shù)b,pow(a,b)=pow(a,b mod phi(n))(mod n)

多少有點似懂非懂吧，氦

拓展歐幾里得算法（差點忘了，歐幾里得算法上面有）：

int exgcd(int a,int b,int? &x,int &y){

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

int d=exgcd(a,b,x,y);

int z=x;x=y;y=z-y*(a/b);

return d;

}

這玩意是給裴屬定理，也就是a*x+b*y=gcd(a,b)一組解

如果遇到普通的a*x+b*y=c，我們可以用上述特殊解找通解

線性同余方程：

a*x=b(mod m),求x

若成立，則y*m=b-a*x（其實是為了后面推算，正常好理解版本為a*x=y*m+b)

我們的推算版：a*x+m*y=b

裴屬定理又來力，將原式代入a*x+b*y=c,如果有解，gcd(a,m)|b

然后先找到a*x0+m*y0=gcd(a,m)

然后x=x0*b/gcd(a,m)，即一個可愛的可背性公式

中國剩余定理

好，先插播一段抽象的文言文（說真的，我覺得迪利克雷卷積更抽象）

今有物，不知其數(shù)，三三數(shù)之，剩二；五五數(shù)之，剩三；七七數(shù)之，剩二。問物幾何？

好了，從前有m1,m2...至mn,它們兩兩互質(zhì)

然后有個m,等于它們?nèi)悠饋?/p>

還有個Mi，等于m/mi

然后是個ti,Mi*ti=1(mod mi)

對于任意正整數(shù)a1,a2...an

有一個{

x=a1(mod m1)

x=a2(mod m2)

...

x=an(mod mn)

}

然后，根據(jù)孫子的中國剩余定理，可得x=a1*M1*t1+a2*M2*t2+...+an*Mn*tn（文本文檔，不知到怎么打sigma見諒）

然而，中國剩余定理只給了個解，最小還得對m取模。。。

Sumdiv(poj1845)

分解A

得到A的B次方的質(zhì)因數(shù)分解式（我能看的懂就行捏

約數(shù)和是就那個公式

然后等比數(shù)列求和

(a+b)%m=(a%m+b%m)%m

(a*b)%m=(a%m*b%m)%m

a/b%m=a%(b*m)/b

一些同余的式子

雖然不太懂但是貌似有點用

哦，逆元的線性打表遞推法

遞推公式：inv[i]=(p-p/i)*inv[p%i]%p)

當pi-1不是9901倍數(shù)時，求出起模9901的乘法逆元

如果是，就為B*ci+1 (mod 9901)

https://blog.csdn.net/weixin_34064653/article/details/93960412

Prime Distance(poj2689)

這道題主要來講就是先篩出sqrt(2e9),也就是大約50000以內(nèi)的素數(shù)

然后所有合數(shù)都一定有這以內(nèi)的質(zhì)因子

其實剩時間還可以只篩sqrt(r)

然后再拿這些數(shù)去篩l至r

然而很顯然你不可能篩50000*1000000，畢竟2開始就沒了一半了。。。

然后就只剩質(zhì)數(shù)了

一個p[1000001]的數(shù)組

true為質(zhì)數(shù) false為合數(shù)

https://tool.4xseo.com/a/8447.html

階乘分解

給定正整數(shù)N(N≤10^6)，把n!分解質(zhì)因數(shù)，輸出出對應(yīng)的pi和ci

先篩出N以內(nèi)質(zhì)數(shù)

然后設(shè)質(zhì)數(shù)P，它的指數(shù)為[n/p]+[n/p^2]....（這玩意其實就是有一個p的搜一遍，兩個p的搜一遍，但兩個在一個中也搜了一遍，所以不需要乘，直接再加一遍即可，后面同理）

當P大于根號N時

只可能有n/p

所以不會有可愛的TLE

https://blog.csdn.net/m0_51841071/article/details/116539396

余數(shù)求和（bzoj1257)

首先，通過思考，可得k mod i=k-[k/i]*i

其實還是經(jīng)常沒有往這方面想，后來發(fā)現(xiàn)這個式子幾乎不思考即可得到，只是甚至沒想過會使用

對于i<=sqrt(k)

每個商不一定連續(xù)但絕對不同，這時i比商的跨度小，因此枚舉i

對于i>=sqrt(k)

每個商連續(xù)且可能有多個，這時i比商的跨度大，因此枚舉商

運用整除以及等差數(shù)列求和算出這部分的余數(shù)

https://blog.csdn.net/giftedpanda/article/details/99844152

Hankson的趣味題（Noip2009)

就一定程度上而言，這道題有點暴力

不論d再大

2e9以內(nèi)它的因數(shù)都可以枚舉

而2e9以內(nèi)整數(shù)約數(shù)之多幾千個，因此不會TLE

https://www.sohu.com/a/162622104_99893619

Visible Lattice Points(poj3090）

首先除去特殊的（1，0）和（0，1）

如果gcd(x,y)!=1

那么它前面一定有經(jīng)歷過點(x/gcd(x,y),y/gcd(x,y))

而想要找一個數(shù)及與它互質(zhì)有多少，phi來了

由于對稱所以乘二還有原點

https://blog.csdn.net/weixin_43874261/article/details/88373682

The Luckist Number(poj3696)

L個8等于8乘L個1等于9分之一的8乘L個9

因此若9*L|8*(pow(10,x)-1)

d=gcd(L,8)

9*L/d|pow(10,x)-1

pow(10,x)=1(mod 9*L/d)

然后根據(jù)我也記不得的定理可知：

若(a,n)=1

使pow(a,x)=1(mod n)的最小的正整數(shù)x為phi(n)的約數(shù)

接著就是x最小為一個phi(9*L/d)的約束，然后，枚舉大法萬歲！

同余方程(NOIP2012)

根據(jù)線性同余方程的知識點，通過套公式可得a*x+b*y=1

exgcd得出a*x0+b*y0=gcd(a,b)的解

接著將其代入公式

x=(x0%b+b)%b

https://www.cnblogs.com/CXCXCXC/p/4752391.html

Strang Way to Express Integers(poj2891)

這道題并沒有說mi之間兩兩互質(zhì)，所以得用exgcd

由于它有n個方程，首先，設(shè)前k-1個方程

此時的m等于m1+m2...+mk-1

而此時，x+tm為前k-1個方程的解

這玩意的成因：對于第k個方程，有x+tm=ak(mod mk),因此，由于題目會成立，所以必定有一個x+tm是前k-1個方程的解

接著，在n次的exgcd后，我們蹭啊蹭，蹭到了最后的解

https://codeleading.com/article/97291181151/