数论整理

求最小公倍数

辗转相除法

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<n;i++)
    {
        if(is_prime[i])
            prime.push_back(i);
        for(int j=0;j<prime.size()&&i*prime[j]<maxn;j++)
        {
            is_prime[i*prime[j]]=false;
            if(i%prime[j]==0)break;
            //i//prime[j]=m,则i*prime[j+1]=m*prime[j]*prime[j+1]=prime[j]*n,且n>i,prime[j]<prime[j+1],因此i*prime[j+1]一定会在未来当i=n时被筛去
            //保证了每个合数仅被它最小的质因子筛除一次，提高效率
        }
    }

求解逆元（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;

数论整理

原文：https://www.cnblogs.com/tldr/p/10877440.html