【数论】【模板】

打算存点数论板子
1.GCD与LCM
辗转相除法：

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

更相减损术：

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

记录一下昨晚的题：传送门添加链接描述

2.质因数分解（唯一分解定理）

void divide(int x){
    for(int i=2;i<=x/i;i++)
        if(x%i==0){
            int s=0;
            while(x%i==0) x/=i,s++;
            cout<<i<<" "<<s<<endl;
        }
    if(x>1) cout<<x<<" "<<1<<endl;
    cout<<endl;
}

3.质数筛
埃氏筛

int pri[N],cnt;
bool st[N];
void prim(int x){
    for(int i=2;i<=x;i++){
        if(!st[i]){
        pri[cnt++]=i;
        for(int j=i+i;j<=x;j+=i)
            st[j]=true;
        }
        
    }
}

欧拉筛

int pri[N],cnt;
bool st[N];
void prim(int x){
    for(int i=2;i<=x;i++){
        if(!st[i]) pri[cnt++]=i;
        for(int j=0;pri[j]<=x/i;j++){
            st[pri[j]*i]=true;
            if(i%pri[j]==0) break;
        }       
    }
}

区间筛
4.试除法求约数

vector<int> get_divisors(int x)
{
    vector<int> res;
    for (int i = 1; i <= x / i; i ++ )
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i) res.push_back(x / i);
        }
    sort(res.begin(), res.end());
    return res;
}

5.约数个数

如果 N = p1^c1 * p2^c2 * … *pk^ck
约数个数： (c1 + 1) * (c2 + 1) * … * (ck + 1)
约数之和： (p1^0 + p1^1 + … + p1^c1) * … * (pk^0 + pk^1 + … + pk^ck)

unordered_map<int, int> primes;

   while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes) res = res * (p.second + 1) % mod;

6.约数之和

unordered_map<int, int> primes;

    while (n -- )
    {
        int x;
        cin >> x;

        for (int i = 2; i <= x / i; i ++ )
            while (x % i == 0)
            {
                x /= i;
                primes[i] ++ ;
            }

        if (x > 1) primes[x] ++ ;
    }

    LL res = 1;
    for (auto p : primes)
    {
        LL a = p.first, b = p.second;
        LL t = 1;
        while (b -- ) t = (t * a + 1) % mod;
        res = res * t % mod;
    }

7.欧拉函数
1 ~ N 中与 N 互质的数的个数被称为欧拉函数

 int a;
        cin>>a;
        int res=a;
        for(int i=2;i<=a/i;i++)
            if(a%i==0){
                res=res/i*(i-1);
                while(a%i==0) a/=i;
            }
        if(a>1) res=res/a*(a-1);
        cout<<res<<endl;

8.筛法求欧拉函数

int prime[N],cnt,phi[N];
bool st[N];

ll get_eulers(int n){
    phi[1]=1;
    for(int i=2;i<=n;i++){
        if(!st[i]){
            prime[cnt++]=i;
            phi[i]=i-1;
        }
        for(int j=0;prime[j]<=n/i;j++){
            st[prime[j]*i]=true;
            if(i%prime[j]==0){
                phi[i*prime[j]]=prime[j]*phi[i];
                break;
            }
            phi[i*prime[j]]=(prime[j]-1)*phi[i];
        }
    }
    ll res=0;
    for(int i=1;i<=n;i++) res+=phi[i];
    return res;
}

9.快速幂

ll ksm(ll a,ll b,ll p){
    ll res=1;
    a%=p;
    while(b){
//&运算当相应位上的数都是1时，该位取1，否则该为0。
        if(b&1)
            res=1ll*res*a%p;//转换为ll型
        a=1ll*a*a%p;
        b>>=1;//十进制下每除10整数位就退一位 
    }
    return res;
}

10.龟速乘
求 a 乘 b 对 p 取模的值。
1≤a,b,p≤10^18

ll cul(ll a,ll b,ll p){
    ll res=0;
    while(b){
        if(b&1)
            res=(res+a)%p;
        a=(a+a)%p;
        b>>=1;
    }
    return res;
}

11.乘法逆元

若整数b，m互质，并且对于任意的整数 a，如果满足b|a，则存在一个整数x，使得a/b≡a∗x(mod m)，则称x为b的模m乘法逆元，记为b−1(mod m)。
b存在乘法逆元的充要条件是b与模数m互质。当模数m为质数时，bm−2即为b的乘法逆元。

cin>>a>>p;
        if(a%p==0) puts("impossible");
        else cout<<ksm(a,p-2,p)<<endl;

12.扩展欧几里得算法

给定n对正整数ai,bi，对于每对数，求出一组xi,yi，使其满足ai∗xi+bi∗yi=gcd(ai,bi)。

int exgcd(int a,int b,int &x,int &y){
    if(!b){
        x=1,y=0;
        return a;
    }
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;
    return d;
}

13.中国剩余定理

给定 2n 个整数a1,a2,…,an和m1,m2,…,mn,求一个最小的非负整数 x，满足 ∀i∈[1,n],x≡mi(mod ai) 。

14.高斯消元

15.矩阵乘法

来自AcWing