目录

求最小公倍数

辗转相除法

gcd(a,b)=>gcd(b,a%b)

ll gcd(ll a,ll b){    if(!b)return a;    else return gcd(b,a%b);}

求素数

埃式筛

//复杂度O(nloglogn)for(long long i=2;i<=n;i++)    {        if(prime[i])        {            for(long long j=i*i;j<=n;j=j+i)//i*i更加高效            {                prime[j]=false;            }        }    }

欧拉筛

for(int i=2;i
    
     i,prime[j]
    

求解逆元（mod N）

扩展欧几里德

void extend_euclid(ll a,ll b,ll &d,ll &x,ll &y){    if(!b)    {        d=a;x=1;y=0;        return;    }    else    {        extend_euclid(b,a%b,d,y,x);        y=y-(a/b)*x;    }}cout<<(x+p)%p;