模版代码：模板代码大全（持续更新ing...）

目录

• 数论
• • 快速幂
  • Lucas 定理
  • 素数筛法
  • • Eratosthenes 筛法
    • Euler 筛法（线性筛法）
  • 质因数分解
  • 求某个数的正约数集合
  • 最大公约数
  • 最小公倍数
  • 欧拉函数
  • 函数筛法
  • • 筛欧拉函数
    • 筛莫比乌斯函数
• 图论
• • 最短路
  • • Dijkstra 单源最短路

数论

快速幂

求 x y m o d p x^y \bmod p xymodp。

long long power(long long x,int y){long long res=1;for(;y;y>>=1){if(y&1)res=res*x%p;x=x*x%p;}return res;}

Lucas 定理

求 C n m m o d p C_n^m \bmod p Cnm​modp

long long fac[p],inv[P];// 此处省略快速幂 power 函数void init(){fac[0]=inv[0]=1;for(int i=1;i<P;++i)fac[i]=fac[i-1]*i%p,inv[i]=power(fac[i],p-2);}long long C(int n,int m,int p){ if(m>n)return 0; return fac[n]*inv[n-m]%p*inv[m]%p;}long long Lucas(int n,int m,int p){if(m==0)return 1;return C(n%p,m%p,p)*Lucas(n/p,m/p,p)%p;}

素数筛法

Eratosthenes 筛法

bool st[N];int primes[N],tot=0;void Eratosthenes(int n){for(int i=2;i<=n;++i){if(st[i])continue;primes[++tot]=i;for(int j=i;j<=n/i;++j)st[i*j]=true;}}

Euler 筛法（线性筛法）

int st[N],primes[N],tot=0;void Euler(int n){for(int i=2;i<=n;++i){if(!st[i])primes[++tot]=st[i]=i;for(int j=1;j<=tot;++j){if(primes[j]>st[i]||primes[j]>n/i)break;st[i*primes[j]]=primes[j];}}}

质因数分解

分解 n n n 的质因数，从小到大依次输出。

for(int i=2;i<=n/i;++i)while(n%i==0)cout<<i<<' ',n/=i;if(n!=1)cout<<n<<' ';

求某个数的正约数集合

从小到大输出 n n n 的所有约数。

vector<int>s,t;for(int i=1;i<=n/i;++i)if(n%i==0){s.push_back(i);if(i!=n/i)t.push_back(n/i);}for(int i=0;i<s.size();++i)cout<<s[i]<<' ';for(int i=t.size()-1;i>=0;--i)cout<<t[i]<<' ';

最大公约数

求 x x x 和 y y y 的最大公约数。

int gcd(int x,int y){return y?gcd(y,x%y):x;}

最小公倍数

求 x x x 和 y y y 的最小公倍数。

//此处省略最大公约数 gcd 函数long long lcm(int x,int y){return(long long)x*y/gcd(x,y);}

欧拉函数

求 φ ( n ) \varphi(n) φ(n)。

int phi(int n){int ans=n;for(int i=2;i<=n/i;++i){int c=0;while(n%i==0)n/=i,c++;if(c)ans=ans/i*(i-1);}if(n!=1)ans=ans/n*(n-1);return ans;}

函数筛法

筛欧拉函数

int st[N],primes[N],phi[N],tot=0;void getPhi(int n){for(int i=2;i<=n;++i){if(!st[i])primes[++tot]=st[i]=i,phi[i]=i-1;for(int j=1;j<=tot;++j){if(primes[j]>st[i]||primes[j]>n/i)break;st[i*primes[j]]=primes[j];if(i%primes[j]==0)phi[i*primes[j]]=phi[i]*primes[j];else phi[i*primes[j]]=phi[i]*(primes[j]-1);}}}

筛莫比乌斯函数

int st[N],primes[N],mu[N],tot=0;void getPhi(int n){for(int i=2;i<=n;++i){if(!st[i])primes[++tot]=st[i]=i,mu[i]=-1;for(int j=1;j<=tot;++j){if(primes[j]>st[i]||primes[j]>n/i)break;st[i*primes[j]]=primes[j];if(i%primes[j]==0)mu[i*primes[j]]=0;else mu[i*primes[j]]=-mu[i];}}}

图论

最短路

省略了一些不优的算法。

Dijkstra 单源最短路

给定一个无负边权的图，求从 s s s 起到所有点的距离。

typedef long long LL;typedef pair<LL,int>PLI;typedef priority_queue<PLI,vector<PLI>,greater<PLI> > PQ;int head[N],Next[M],ver[M];LL val[M],dist[N];bool vis[N];void dijkstra(int s){ for(int i=1;i<=n;++i)dist[i]=(1u<<31)-1; memset(vis,false,sizeof vis); pq=PQ(); dist[s]=0,pq.push({0,s}); while(!pq.empty()){ int u=pq.top().second; pq.pop(); if(vis[u])continue; vis[u]=1; for(int i=head[u];i;i=Next[i]){ int v=ver[i]; if(!vis[v]&&dist[u]+val[i]<dist[v])dist[v]=dist[u]+val[i],pq.push({dist[v],v}); } } for(int i=1;i<=n;++i)cout<<dist[i]<<' ';}