数论

方杰123 · 2022-03-04 20:55:33 · 个人记录

1.CRT中国剩余定理

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int N=21;
int read(){
    int x=0,f=1;char c=getchar();
    while(c>'9' || c<'0'){if(c=='-')f=-1;c=getchar();}
    while(c>='0' && c<='9'){x=(x<<1)+(x<<3)+(c^48);c=getchar();}
    return x*f;
}
int ans,n,Mod[N],Remainder[N],MultiplyContinuously=1,Condition[N];
int exgcd(int a,int b,int &x,int &y){
    if(b==0){x=1,y=0;return a;}
    int d=exgcd(b,a%b,y,x);
    y-=a/b*x;return d;
}
signed main(){
    n=read();
    for(int i=1;i<=n;i++)Mod[i]=read(),Remainder[i]=read(),MultiplyContinuously*=Mod[i];
    for(int i=1;i<=n;i++)Condition[i]=MultiplyContinuously/Mod[i];
    for(int i=1;i<=n;i++){
        int t1=0,t2=0;
        int Dustbin=exgcd(Condition[i],Mod[i],t1,t2);
        t1=(t1%Mod[i]+Mod[i])%Mod[i];
        ans+=t1*Condition[i]*Remainder[i];
    }
    printf("%lld\n",ans%MultiplyContinuously);
    return 0;
}

2.拓展欧几里德

int exgcd(int a,int b,int &x,int &y){
    if(b==0){x=1;y=0;return a;}
    int d=exgcd(b,a%b,y,x);//d是最大公约数
    y-=a/b*x;return d;
}

对于ax+by=1 ，
有解时1\%gcd(a,b)=0 ，
得到bx_2+(a-a/b\times b)y_2=1 ，
此时x=y_2,y=x_2-a/b\times y2 ，
用辗转相除法得到最终b=0时，此时a即为gcd(a,b)，解为x=1,y=0。
解出最小解x_0。

此时y=(1-ax)/b，如果x要增加，那么保持y为整数，则x应加上b的倍数（因为gcd(a,b)=1，所以乘上a并无用） 然后得到x_i=x_0+kb，
要得到最小正整数解x_i，只要x_i=(x_0\%b+b)\%b。(如果b小于0:b=-b)

一般题目里是ax+by=C，（C是gcd(a,b)的倍数的话，有解）
解出ax+by=1后， 可以得到 axC+bxC=C，axC/(gcd(a,b))+bxC/(gcd(a,b))=C/(gcd(a,b)， 所以x乘上C/(gcd(a,b))。解出一组x后，其他解为x_i=x_0+kb/(gcd(a,b)。

证明：

所以x_i=x_0+kb/(gcd(a,b)。（PS：不太懂2022.10.11）

3.质因数分解

普通的质因数分解是O(\sqrt n)的。

int tmp=x;
for(int i=2;i*i<=x;i++){
    if(tmp%i)continue;
    cout<<tmp<<" ";
    while(tmp%i==0)tmp/=i;
}
if(tmp>1)cout<<tmp<<" ";

当然你可以打质数筛优化这个过程O(faster)。

for(int j=1;prime[j]<=sqrt(a[i]);j++){
    while(tmp%prime[j]==0){
        ans+=check(prime[j]);
        tmp/=prime[j];
    }
}
if(tmp>1)ans+=check(tmp);

4.线性求乘法逆元

首先，p为质数。

inv[1]=1;
inv[i]=(p-p/i)*(inv[p%i])%p;

5.lucas定理

p为质数。

6.欧拉函数

套路是找到一个gcd(a,b)=c，变为gcd(a/c,b/c)=1。

phi[1]=1;bk[1]=1;
for(int i=2;i<=maxn;i++){
    if(!bk[i]){
        prime[++tot]=i;
        phi[i]=i-1;
    }
    for(int j=1;j<=tot;j++){
        if(i*prime[j]>maxn)break;
        bk[i*prime[j]]=1;
        phi[i*prime[j]]=phi[i]*(i%prime[j]?prime[j]-1:prime[j]);
        if(i%prime[j]==0)break;
    }
}

你也可以质因数分解做（也可以用质数筛优化）

int phi(int x){
    int ans=x;int tmp=x;
    for(int i=2;i*i<=x;i++){
        if(tmp%i)continue;
        ans=ans/i*(i-1);
        while(tmp%i==0)tmp/=i;
    }
    if(tmp>1)ans=ans/tmp*(tmp-1);
    return ans;
}

7.组合数公式

1. C(n,k)=C(n,n-k)
2. C(n,k)+C(n,k+1)=C(n+1,k+1)
3. C(n,k+1)=C(n,k)\times (n-k)/(k+1)

8.欧拉筛

for(int i=2;i<=n;i++){
    if(bk[i]==0)prime[++tot]=i;
    for(int j=1;j<=tot;j++){
        if(prime[j]*i>n)break;
        bk[prime[j]*i]=1;
        if(i%prime[j]==0)break;
    }
}

9.高斯消元

10. 费马小定理

若x是a\mod p下的逆元，则x=a^{p-2}(p为质数) 。

11.拓欧求逆元

若x是a\mod p下的逆元，则x\times a=1(\mod p)，所以ax+py=1，那么用拓欧即可求出x

12.除法分块

13.类欧几里得算法

2147483647.其他

立方差公式：a^3-b^3=(a-b)(a^2+ab+b^2) 。