目录

模板

快速幂

long long quick_power(long long a,long long b,long long c){    long long ans=1;    a=a%c;    while(b!=0)    {        if(b&1)            ans=(ans*a)%c;        b>>=1;        a=(a*a)%c;    }    return ans;}

快速乘

ll qmul(ll a,ll b,ll m){    ll ans=0;    ll k=a;    ll f=1;  //f用来存负号    if(k<0){        f=-1;        k=-k;    }    if(b<0){        f*=-1;        b=-b;    }    while(b){        if(b&1)            ans=(ans+k)%m;        k=(k+k)%m;        b>>=1;    }    return ans*f;}

素数筛

const int N = 1e7 + 5;bool isprime[N];//isprime[i]表示i是不是质数int prime[N];//prime[N]用来存质数  从1开始int tot=1;//tot表示[2，N]之间质数的数量void init(){    for(int i=2;i

GCD

int gcd(int a,int b){    return b==0?a:gcd(b,a%b);}

当然这个GCD是手写的，C++库里面也有一个GCD，很好用的，用库里面的就不需要自己手写函数了。

int c=__gcd(a,b);//c即为a和b的最大公约数

LCM

当然既然讲了GCD，那么LCM也是必要的

int lcm(int a,int b){    a=a/gcd(a,b)*b;  //注意，这里应该是先除再乘，因为先乘的话可能会爆范围    return a;}

EXGCD

int exGcd(int a,int b,int &x,int &y){    if(b==0){        x=1;        y=0;        return a;    }    int r=exGcd(b,a%b,x,y);    int tmp=x;    x=y;    y=tmp-a/b*y;    return r;}