一、法雷序列（莫比乌斯反演/欧拉函数前缀和）
莫比乌斯反演：
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int p[1000010],vis[1000010],mu[1000100],cnt; void get() { memset(vis,0,sizeof(vis)); cnt=0; vis[1]=1; mu[1]=1; for(int i=2; i<=1000000; i++) { if(!vis[i]) { p[cnt++]=i; mu[i]=-1; } for(int j=0; j<cnt; j++) { if(p[j]*i>1000000) { break; } vis[i*p[j]]=1; if(i%p[j]==0) { mu[i*p[j]]=0; break; } else { mu[i*p[j]]=-mu[i]; } } } } int main() { int a,b,c,d,k,n; get(); scanf("%d",&n); a=1; b=1; b=n; d=n; k=1; if(b>d) { swap(b,d); } long long ans1=0; for(int i=1; i<=b; i++) { ans1+=(long long)mu[i]*(b/i)*(d/i); } long long ans2=0; for(int i=1; i<=b; i++) { ans2+=(long long)mu[i]*(b/i)*(b/i); } ans1-=ans2/2; printf("%lld ",ans1-1); }
欧拉函数前缀和：
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int vis[1000010],prime[1000010],phi[1000010],t,n; long long sum[1000010]; void get() { for(int i=2;i<=1000000;i++) { if(!vis[i]) { prime[++t]=i; phi[i]=i-1; } for(int j=1;j<=t;j++) { if(prime[j]*i>1000000) { break; } vis[prime[j]*i]=1; phi[prime[j]*i]=phi[i]*(prime[j]-1); if(i%prime[j]==0) { phi[prime[j]*i]=phi[i]*prime[j]; break; } } } } int main() { get(); scanf("%d",&n); for(int i=1;i<=n;i++) { sum[i]=sum[i-1]+phi[i]*1ll; } printf("%lld ",sum[n]); }
二、组合数取模（线性求模数阶乘，阶乘逆元）
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define int long long using namespace std; int mod,fac[100010],inv[100010],n,m; int kasumi(int a,int b) { int ans=1; while(b) { if(b&1) { ans=((ans%mod)*a)%mod; } a=((a%mod)*a)%mod; b>>=1; } return ans; } signed main() { scanf("%lld%lld%lld",&m,&n,&mod); fac[1]=1; int lim=min(mod-1,100000ll); for(int i=2;i<=lim;i++) { fac[i]=(fac[i-1]%mod)*i%mod; } inv[lim]=kasumi(fac[lim],mod-2); for(int i=lim-1;i>=1;i--) { inv[i]=((inv[i+1]%mod)*(i+1))%mod; } printf("%lld ",((fac[m]*inv[n])%mod*inv[m-n])%mod); }
三、乘法逆元（扩展欧几里得）
#include<cmath> #include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; long long a,c; long long gcd(long long a,long long b) { if(a%b==0) { return b; } return gcd(b,a%b); } void exgcd(long long a,long long b,long long &x,long long &y) { if(b==0) { x=1; y=0; return ; } exgcd(b,a%b,x,y); int tmp=x; x=y; y=tmp-a/b*y; } int main() { scanf("%lld%lld",&a,&c); long long x,y; if(gcd(a,c)!=1) { puts("-1"); return 0; } exgcd(a,c,x,y); if(x<0) { while(x<0) x+=c; } printf("%lld ",x); }
四、素数个数和（线性筛素数）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> using namespace std; int prime[10000010],vis[10000010],cnt,n; void get(int n) { for(int i=2;i<=n;i++) { if(!vis[i]) { prime[++cnt]=i; } for(int j=1;j<=cnt;j++) { if(prime[j]*i>n) { break; } vis[prime[j]*i]=1; if(i%prime[j]==0) { break; } } } } int main() { scanf("%d",&n); get(n); printf("%d ",cnt); }
五、大数求欧拉函数（sqrt(n)暴力）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define N 100000 using namespace std; long long n,prime[100010],vis[100010],cnt; int check(long long x) { for(int i=2;i*i<=x;i++) { if(x%i==0) { return 0; } } return 1; } long long get_phi(long long x) { long long ans=x; if(check(x)) { ans=ans/x*(x+1); } for(int i=2;i*i<=x;i++) { if(x%i==0) { if(check(i)) { ans=ans/i*(i-1); } if(check(x/i)&&x/i!=i) { ans=ans/(x/i)*(x/i-1); } } } return ans; } int main() { scanf("%lld",&n); n==1?puts("1"):printf("%lld ",get_phi(n)); }
六、网格的走法（卡特兰数）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 using namespace std; long long fac[200010],inv[200010],n; long long kasumi(long long a,long long b) { long long ans=1; while(b) { if(b&1) { ans=ans*a%mod; } a=a*a%mod; b>>=1; } return ans; } int main() { scanf("%lld",&n); fac[1]=1; for(int i=2;i<=2*n;i++) { fac[i]=fac[i-1]*i%mod; } inv[2*n]=kasumi(fac[2*n],mod-2); for(int i=2*n-1;i>=1;i--) { inv[i]=inv[i+1]*(i+1)%mod; } printf("%lld ",((fac[2*n]*inv[n])%mod*inv[n+1])%mod); }
七、又一个小球问题（第一类斯特林数）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 using namespace std; long long f[1010][1010],n,m; int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { f[i][0]=0ll; f[i][i]=1ll; } f[0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { f[i][j]=f[i-1][j-1]+f[i-1][j]*1ll*(i-1); f[i][j]%=mod; } } printf("%lld ",f[n][m]); }
八、叕一个小球问题（第二类斯特林数）
#include<cstdio> #include<cstring> #include<iostream> #include<algorithm> #define mod 1000000007 using namespace std; long long f[1010][1010],n,m; int main() { scanf("%lld%lld",&n,&m); for(int i=1;i<=n;i++) { f[i][0]=0ll; f[i][i]=1ll; } f[0][0]=1; for(int i=1;i<=n;i++) { for(int j=1;j<i;j++) { f[i][j]=f[i-1][j-1]+f[i-1][j]*1ll*j; f[i][j]%=mod; } } printf("%lld ",f[n][m]); }