一些简单的数论模版

一：gcd、lcm

辗转相除法求 gcd。

int gcd(int a,int b){
    return b?gcd(b,a%b):a;
}
int lcm(int a,int b){
    return a*b/gcd(a,b);
}

二：线性筛求质数

void init(int n){
    for(int i=2;i<=n;i++){
        if(!vis[i]) prime[++cnt]=i;
        for(int j=1;prime[j]*i<=n;j++){
            vis[i*prime[j]]=1;
            if(i%prime[j]==0) break;
        }
    }
}

三：线性筛求欧拉函数

经典例题（GCD SUM）

//luogu P2398
#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=1e5+10;

int n,phi[N],prime[N],vis[N],cnt;

void init(int n){//线性筛求欧拉函数
phi[1]=1;
for(int i=2;i<=n;i++){
if(!vis[i]) prime[++cnt]=i,phi[i]=i-1;
for(int j=1;prime[j]*i<=n;j++){
vis[i*prime[j]]=1;
if(i%prime[j]==0){phi[i*prime[j]]=phi[i]*prime[j];break;}
phi[i*prime[j]]=phi[i]*phi[prime[j]];
}
}
}

signed main(){

cin>>n;init(n);int ans=0;
for(int d=1;d<=n;d++) ans+=(n/d)*(n/d)*phi[d];
cout<<ans<<endl;

return 0;
}

四：质因数分解

经典例题（细胞分裂）

#include<bits/stdc++.h>
using namespace std;
#define int long long
const int N=30010,INF=1e10;

int n,m1,m2,cnt[N],prime[N],tot;

void solve(int x){//对x质因数分解
for(int i=2;i*i<=x;i++){
if(x%i==0){
prime[++tot]=i;
while(x%i==0) x/=i,cnt[tot]++;
}
}
if(x!=1) prime[++tot]=x,cnt[tot]=1;
for(int i=1;i<=tot;i++) cnt[i]*=m2;
}

signed main(){

ios::sync_with_stdio(false);
cin>>n>>m1>>m2;
solve(m1);int ans=INF;
for(int i=1;i<=n;i++){
int x;cin>>x;int k=0;
for(int j=1;j<=tot;j++){
if(x%prime[j]!=0){k=INF;break;}
int c=0;
while(x%prime[j]==0) x/=prime[j],c++;
k=max(k,cnt[j]/c+(cnt[j]%c==0?0:1));
}
ans=min(ans,k);
}
if(ans==INF) cout<<-1<<endl;
else cout<<ans<<endl;

return 0;
}

五：扩展欧几里得算法

用处：求解线性同余方程。

例题：有理数取余，同余方程，青蛙的约会。

附 P1516青蛙的约会 代码：

#include<bits/stdc++.h>
using namespace std;
#define int long long
int X,Y,m,n,L,a,b,x,y;

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

signed main(){

cin>>X>>Y>>m>>n>>L;
a=m-n,b=Y-X;
if(a<0) a=-a,b=-b;
int d=exgcd(a,L,x,y);
if(b%d!=0) cout<<"Impossible"<<endl;
else{
int t=L/d;
x=((x*(b/d))%t+t)%t;
cout<<x<<endl;
}

return 0;
}

六：数论分块

经典例题（余数求和），算是为数不多的不用莫反的数论分块题了，适合做简单的模版。

#include<bits/stdc++.h>
using namespace std;
#define int long long

int n,k;

signed main(){

cin>>n>>k;
int ans=n*k;
for(int l=1,r;l<=n;l=r+1){
if(k/l<=0) break;
r=min(k/(k/l),n);
ans-=(r-l+1)*(l+r)/2*(k/l);
}
cout<<ans<<endl;

return 0;
}

七：线性求逆元

模版题

关键式子：

inv[1]=1;
for(int i=2;i<=n;i++) inv[i]=(p-p/i)*inv[p%i]%p;

原文地址：https://blog.csdn.net/summ1ts/article/details/142703435

免责声明：本站文章内容转载自网络资源，如本站内容侵犯了原著者的合法权益，可联系本站删除。更多内容请关注自学内容网（zxcms.com）！