①乘法逆元
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long LL n,M; inline LL fd(){ LL s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } inline LL qsm(LL x,LL y){ LL base = 1; while(y){ if(y&1) base = (1ll*base%M*x%M)%M; x = (x%M*x%M)%M; y>>=1; } return base; } int main() { freopen("P3811.in","r",stdin); freopen("P3811.out","w",stdout); n = fd(),M = fd(); for(re LL i=1;i<=n;++i) printf("%lld ",(qsm(i,M-2)%M+M)%M); return 0; }
②exgcd
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long LL n,M,x1,y1,x2,y2; inline LL fd(){ LL s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void exgcd(LL x,LL y){ if(!y){ x1 = 1;y1 = 0; return; } exgcd(y,x%y); x2 = x1,y2 = y1; x1 = y2; y1 = x2-x/y*y2; } int main() { freopen("P3811.in","r",stdin); freopen("P3811.out","w",stdout); n = fd(),M = fd(); for(re LL i=1;i<=n;++i){ exgcd(i,M); printf("%lld ",(x1%M+M)%M); } return 0; }
③线性递推逆元
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL int const LL N = 3e6+5; LL n,M,Inv[N]; inline LL fd(){ LL s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int main() { freopen("P3811.in","r",stdin); freopen("P3811.out","w",stdout); n = fd(),M = fd(); Inv[1] = 1; printf("%d ",Inv[1]); for(re int i=2;i<=n;++i){ Inv[i] = ((1ll*-Inv[M%i]*(M/i))%M+M)%M; printf("%d ",Inv[i]); } return 0; }
④线性筛素数
#include<iostream> #include<cstdio> using namespace std; #define e exit(0) #define re register const int M = 1e7+5; int n,m,lx,vis[M],Q[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int main() { n = fd(),m = fd(); vis[1] = 1; for(re int i=2;i<=n;++i){ if(!vis[i]) Q[++lx] = i; for(re int j=1;j<=lx;++j){ if(i*Q[j] > n) break; vis[i*Q[j]] = 1; if(i % Q[j] == 0) break; } } while(m--){ int x = fd(); if(vis[x]) printf("No "); else printf("Yes "); } return 0; }
⑤线性筛求欧拉函数
#include<iostream> #include<cstdio> using namespace std; #define e exit(0) #define re register const int M = 1e7+5; int n,m,lx,vis[M],Q[M]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int main() { n = fd(),m = fd(); vis[1] = 1; for(re int i=2;i<=n;++i){ if(!vis[i]) Q[++lx] = i; for(re int j=1;j<=lx;++j){ if(i*Q[j] > n) break; vis[i*Q[j]] = 1; if(i % Q[j] == 0) break; } } while(m--){ int x = fd(); if(vis[x]) printf("No "); else printf("Yes "); } return 0; }
⑥单个求欧拉函数
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register int n; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int phi(int x){ int ans = x; for(re int i=2;i*i<=x;++i){ if(x % i == 0){ ans = ans - ans/i; while(x%i == 0) x /= i; } } if(x > 1) ans = ans - ans/x; return ans; } int main() { freopen("kkk.in","r",stdin); freopen("kkk.out","w",stdout); n = fd(); printf("%d",phi(n)); return 0; }
⑦矩阵快速幂
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register const int M = 1e9+7; int n; long long k; struct JZ{ int a[101][101]; JZ(){memset(a,0,sizeof(a));} JZ operator *(const JZ &x) const{ JZ s; for(re int k=1;k<=n;++k) for(re int i=1;i<=n;++i) for(re int j=1;j<=n;++j) s.a[i][j] = (s.a[i][j]%M+1ll*a[i][k]*x.a[k][j]%M)%M; return s; } }x; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } JZ qsm(JZ x,long long y){ JZ base; for(re int i=1;i<=n;++i) base.a[i][i] = 1; while(y){ if(y&1) base = base*x; x = x*x; y>>=1; } return base; } int main() { freopen("P3390.in","r",stdin); freopen("P3390.out","w",stdout); n = fd(); scanf("%lld",&k); for(re int i=1;i<=n;++i) for(re int j=1;j<=n;++j) x.a[i][j] = fd(); x = qsm(x,k); for(re int i=1;i<=n;++i){ for(re int j=1;j<=n;++j) printf("%d ",x.a[i][j]); printf(" "); } return 0; }
⑧组合数递推
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register int n,c[501][501]; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int main() { freopen("k1.in","r",stdin); freopen("k1.out","w",stdout); n = fd(); c[1][0] = c[1][1] = 1; for(re int i=2;i<=n;++i){ c[i][0] = 1; for(re int j=1;j<=i;++j) c[i][j] = c[i-1][j]+c[i-1][j-1]; } return 0; }
⑨不定方程
#include<iostream> #include<cstring> #include<cstdio> #include<cmath> using namespace std; #define e exit(0) #define re register int a,b,c,g,x,y,x1,Y1,x2,y2; inline int fd(){ int s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } int gcd(int x,int y){ if(!y) return x; else return gcd(y,x%y); } void exgcd(int a,int b){ if(!b){ x1 = 1,Y1 = 0; return; } exgcd(b,a%b); x2 = x1,y2 = Y1; x1 = y2; Y1 = x2-a/b*y2; } int main() { freopen("k1.in","r",stdin); freopen("k1.out","w",stdout); a = fd(),b = fd(),c = fd(); g = gcd(a,b); exgcd(a,b); x1 = x1*(c/g),Y1 = Y1*(c/g); for(re int k=0;k<=100;++k){ x = x1+k*(b/g); y = Y1+k*(a/g); printf("%d %d ",x,y); } return 0; }
中国剩余定理
#include<iostream> #include<cstring> #include<cstdio> using namespace std; #define e exit(0) #define re register #define LL long long const LL N = 5e5+5; LL n,M=1,x1,y1,x2,y2,a[N],b[N],ans; inline LL fd(){ LL s=1,t=0;char c=getchar(); while(c<'0'||c>'9'){if(c=='-')s=-1;c=getchar();} while(c>='0'&&c<='9'){t=t*10+c-'0';c=getchar();} return s*t; } void exgcd(LL a, LL b){ if(!b){ x1 = 1,y1 = 0; return; } exgcd(b,a%b); x2 = x1,y2 = y1; x1 = y2; y1 = x2-a/b*y2; } int main() { freopen("kkk.in","r",stdin); freopen("kkk.out","w",stdout); n = fd(); for(re LL i=1;i<=n;++i){ a[i] = fd(),b[i] = fd(); M *= a[i]; } for(re LL i=1;i<=n;++i){ LL mi = M/a[i]; exgcd(mi,a[i]); LL k = x1; ans += k*mi*b[i]; } ans = ((ans%M)+M)%M; printf("%lld",ans); return 0; }