整理的算法模板合集： ACM模板

---

目录

一：【质数】1.【暴力判】2.【Miller Rabin】3.【埃氏筛】 4.【欧拉筛】二：【约数】1.【欧几里得 (gcd)】2.【欧拉函数（埃氏筛）】3.【欧拉函数（欧拉筛）】 三：【同余】1.【逆元】(1).【递推】(2).【快速幂】3.【扩展欧拉定理】5.【中国剩余定理 (CRT)】6.【扩展中国剩余定理 (EXCRT)】7.【拔山盖世 / 大步小步 / BSGS (Baby Steps Giant Steps)】8.【扩展 BSGS (EXBSGS)】9.【二次剩余】10.【N 次剩余】 四：【类欧几里得算法】五：【各类反演及数论筛法】1.【莫比乌斯函数(Mobius)】2.【杜教筛】(1).【map 记忆化】(2).【数组记忆化】3.【最值反演 (Min-Max容斥)】

一：【质数】

1.【暴力判】

【模板】素数、コンテスト、素数 [AT807]

#include<cstdio> #include<cmath> int x; inline bool judge(int n){ if(n<4)return 1; if(n%2==0)return 0; int half=sqrt(n); for(int i=3;i<=half;i+=2) if(n%i==0)return 0; return 1; } int main(){ scanf("%d",&x); puts(judge(x)?"YES":"NO"); }

2.【Miller Rabin】

【模板】质数判定 [Loj143]

#include<cstdio> #define LL long long #define Re register LL LL n,prime[10]={2,3,5,7,11,13,17,19,23,29}; inline LL cf(Re x,Re k,Re P){ Re s=0; while(k){ if(k&1)(s+=x)%=P; (x<<=1)%=P,k>>=1; } return s%P; } inline LL mi(Re x,Re k,Re P){ Re s=1; while(k){ if(k&1)s=cf(s,x,P)%P; x=cf(x,x,P)%P,k>>=1; } return s%P; } inline bool Miller_Rabin(Re x){ Re s=0,t=x-1; if(x==2)return 1; if(x<2||!(x&1))return 0; while(!(t&1))s++,t>>=1; for(Re i=0;i<10&&prime[i]<x;++i){ Re a=prime[i],b=mi(a,t,x); for(Re j=1,k;j<=s;++j){ k=cf(b,b,x); if(k==1&&b!=1&&b!=x-1)return 0; b=k; } if(b!=1)return 0; } return 1; } int main(){ while(scanf("%lld",&n)!=EOF)puts(Miller_Rabin(n)?"Y":"N"); }

【模板】PON - Prime or Not [SP288]

3.【埃氏筛】

【模板】线性筛素数 [P3383]

#include<algorithm> #include<cstdio> #define Re register int using namespace std; const int N=1e7+3; int n,x,T,cnt,pri[N/3];bool pan[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline void get_pri(Re N){ pan[0]=pan[1]=1; for(Re i=2;i<=N;i++) if(!pan[i]){ pri[++cnt]=i; for(Re j=i;j<=N/i;j++)pan[i*j]=1; } } int main(){ in(n),in(T),get_pri(n); while(T--)in(x),puts(pan[x]?"No":"Yes"); }

4.【欧拉筛】

【模板】线性筛素数

#include<cstdio> #include<ctime> const int N=1e6; int cnt,i,j,pri[N/3];bool pan[N+1]; inline void get_pri(){ pan[0]=pan[1]=1; for(i=2;i<=N;++i){ if(!pan[i])pri[++cnt]=i; for(j=1;j<=cnt&&i*pri[j]<=N;++j){ pan[i*pri[j]]=1; if(i%pri[j]==0)break; } } } int main(){ get_pri(); for(j=0,i=1;i<=cnt;++i)printf("%d ",pri[i]); }

二：【约数】

1.【欧几里得 (gcd)】

#include<algorithm> #include<cstdio> int a,b; inline int gcd(Re a,Re b){return (!b)?a:(a%b==0?b:gcd(b,a%b));} //来自某大佬无比魔性的诡异写法（至今未看懂）： inline int GCD(int a,int b){while(b^=a^=b^=a%=b);return a;} int main(){ while(scanf("%d%d",&a,&b)) printf("%d\n",gcd(a,b)); }

2.【欧拉函数（埃氏筛）】

#include<cstdio> const int N=1e6; int cnt,n=N,phi[N/3],pan[N],pri[N]; inline void get_phi(){ pan[0]=pan[1]=1,phi[1]=1; for(int i=2;i<=n;i++)if(!phi[i]){ for(int j=i;j<=n;j+=i){ if(!phi[j])phi[j]=j; phi[j]=phi[j]/i*(i-1); } } } int main(){ get_phi(); for(int i=1;i<=n;++i)printf("%d: %d\n",i,phi[i]); }

3.【欧拉函数（欧拉筛）】

#include<cstdio> const int N=1e6; int cnt,i,j,pan[N+1],pri[N/3],phi[N+1]; inline void get_phi(){ pan[0]=pan[1]=1,phi[1]=1; for(i=2;i<=N;++i){ if(!pan[i])pri[++cnt]=i,phi[i]=i-1; for(j=1;j<=cnt&&i*pri[j]<=N;++j){ pan[i*pri[j]]=1; if(i%pri[j])phi[i*pri[j]]=phi[i]*(pri[j]-1); else{phi[i*pri[j]]=phi[i]*pri[j];break;} } } } int main(){ get_phi(); for(i=1;i<=N;++i)printf("%d: %d\n",i,phi[i]); }

三：【同余】

1.【逆元】

【模板】乘法逆元

(1).【递推】

#include<cstdio> #define LL long long #define Re register int const int N=3e6+3; int n,P,inv[N]; int main(){ // freopen("123.txt","r",stdin); scanf("%d%d",&n,&P); inv[1]=1; for(Re i=2;i<=n;++i)inv[i]=(LL)(P-P/i)*inv[P%i]%P; for(Re i=1;i<=n;++i)printf("%d\n",inv[i]); }

(2).【快速幂】

#include<cstdio> #define LL long long #define Re register int int n,P; inline int inv(Re x,Re P){ Re s=1,k=P-2; while(k){ if(k&1)s=(LL)s*x%P; x=(LL)x*x%P,k>>=1; } return s%P; } int main(){ scanf("%d%d",&n,&P); for(Re i=1;i<=n;++i)printf("%d\n",inv(i,P)); }

3.【扩展欧拉定理】

【模板】扩展欧拉定理（abmodm）

#include<cstdio> #include<cctype> #define LL long long #define Re register LL LL i,a,b,m,x,s,phi,flag;char c; inline LL cf(Re x,Re k){ Re s=0; while(k){ if(k&1)(s+=x)%=m; (x<<=1)%=m,k>>=1; } return s; } int main(){ scanf("%lld%lld",&a,&m);phi=x=m; for(i=2;i*i<=m;++i) if(!(x%i)){phi-=phi/i;while(!(x%i))x/=i;} if(x>1)phi-=phi/x; while(!isdigit(c=getchar())); while(isdigit(c))flag|=((b=(b<<1)+(b<<3)+(c^48))>=phi),b%=phi,c=getchar(); b+=flag?phi:0;x=1; while(b){if(b&1)x=cf(x,a)%m;a=cf(a,a)%m,b>>=1;} printf("%lld",x); } 4.【扩展欧几里得 (Exgcd)】 【模板】同余方程 [P1082] [P1082] #include<cstdio> #define Re register int int a,b,x,y; inline void exgcd(Re a,Re b,Re &x,Re &y){ if(!b){x=1,y=0;return;} exgcd(b,a%b,x,y);Re x0=x,y0=y; x=y0,y=x0-a/b*y0;return; } int main(){ scanf("%d%d",&a,&b),exgcd(a,b,x,y); printf("%d\n",(x%b+b)%b); }

5.【中国剩余定理 (CRT)】

【模板】猜数字

#include<cstdio> #define LL long long #define Re register LL const int N=13; LL n,ans,lcm=1,a[N],m[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline void exgcd(Re a,Re b,Re &x,Re &y){ if(!b){x=1,y=0;return;} exgcd(b,a%b,x,y);Re x0=x,y0=y; x=y0,y=x0-a/b*y0;return; } inline LL cf(Re x,Re k,Re P){ Re s=0; while(k){ if(k&1)(s+=x)%=P; (x+=x)%=P,k>>=1; } return s; } int main(){ // freopen("123.txt","r",stdin); in(n); for(Re i=1;i<=n;++i)in(m[i]),in(a[i]),lcm*=m[i]; for(Re i=1;i<=n;++i){ Re x,y,M=lcm/m[i];exgcd(M,m[i],x,y);//M[i]*inv+m[i]*y=1 x=(x%m[i]+m[i])%m[i],(ans+=cf(cf(a[i],M,lcm),x,lcm))%=lcm; } printf("%lld\n",ans); }

6.【扩展中国剩余定理 (EXCRT)】

【模板】扩展中国剩余定理（EXCRT）

#include<cstdio> #define LL long long #define Re register LL const int N=1e5+3; LL n,ans,lcm=1,a[N],m[N]; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline LL exgcd(Re a,Re b,Re &x,Re &y){ if(!b){x=1,y=0;return a;} Re gcd=exgcd(b,a%b,x,y);Re x0=x,y0=y; x=y0,y=x0-a/b*y0;return gcd; } inline LL cf(Re x,Re k,Re P){ Re s=0; while(k){ if(k&1)(s+=x)%=P; (x+=x)%=P,k>>=1; } return s; } int main(){ // freopen("123.txt","r",stdin); in(n); for(Re i=1;i<=n;++i)in(m[i]),in(a[i]),lcm*=m[i]; ans=a[1]%m[1],lcm=m[1]; for(Re i=2;i<=n;++i){//ans+lcm*k=a[i](mod m[i]) -> lcm*k=a[i]-ans(mod m[i]) -> lcm*k+m[i]*y=a[i]-ans Re c=((a[i]-ans)%m[i]+m[i])%m[i],x,y; Re gcd=exgcd(lcm,m[i],x,y); Re k=cf(x,c/gcd,m[i]/gcd); ans+=lcm*k,lcm*=m[i]/gcd,ans=(ans%lcm+lcm)%lcm; } printf("%lld\n",ans); }

7.【拔山盖世 / 大步小步 / BSGS (Baby Steps Giant Steps)】

#include<algorithm> #include<cstdio> #include<cmath> #include<map> #define LL long long #define Re register int using namespace std; const int N=1e5+3; int x,y,m,P;map<int,int>B; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } //x^k = y (mod P) //k = am-b (m=sqrt(P)+1, a\in[1,m], b\in[0,m-1]) //(x^m)^a = y x^b (mod P) inline int mi(Re x,Re k){ Re s=1; while(k){ if(k&1)s=(LL)s*x%P; x=(LL)x*x%P,k>>=1; } return s; } int main(){ // freopen("123.txt","r",stdin); in(P),in(x),in(y),m=sqrt(P)+1; for(Re b=0,s=y;b<m;++b)B[s]=b,s=(LL)s*x%P; Re tmp=mi(x,m); for(Re a=1,s=1;a<=m;++a){ s=(LL)s*tmp%P; if(B.find(s)!=B.end()){printf("%d\n",a*m-B[s]);return 0;} } puts("no solution"); }

8.【扩展 BSGS (EXBSGS)】

【模板】扩展 BSGS [P4195]

#include<algorithm> #include<cstdio> #include<cmath> #include<map> #define LL long long #define Re register int using namespace std; int x,y,z;map<int,int>B; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline int mi(Re x,Re k,Re P){ Re s=1; while(k){ if(k&1)s=(LL)s*x%P; x=(LL)x*x%P,k>>=1; } return s; } inline int gcd(Re a,Re b){return !b?a:gcd(b,a%b);} inline void exBSGS(Re x,Re y,Re P){ if(y==1){puts("0");return;} Re d=gcd(x,P),tmp=1,t=0; while(d!=1){ if(y%d){puts("No Solution");return;} ++t,y/=d,P/=d,tmp=(LL)tmp*(x/d)%P; if(y==tmp){printf("%d\n",t);return;} d=gcd(x,P); } Re m=sqrt(P)+1;B.clear(); for(Re b=0,s=y;b<m;++b)B[s]=b,s=(LL)s*x%P; Re s=tmp;tmp=mi(x,m,P); for(Re a=1;a<=m;++a){ s=(LL)s*tmp%P; if(B.find(s)!=B.end()){printf("%d\n",a*m-B[s]+t);return;} } puts("No Solution"); } int main(){ // freopen("123.txt","r",stdin); while(1){ in(x),in(y),in(z); if(!x&&!y&&!z)break; exBSGS(x,z,y); } }

9.【二次剩余】

【模板】二次剩余 [P5491]

#include<algorithm> #include<cstring> #include<cstdio> #define LL long long #define Re register int using namespace std; int n,T,P,W,det; inline void in(Re &x){ int f=0;x=0;char c=getchar(); while(c<'0'||c>'9')f|=c=='-',c=getchar(); while(c>='0'&&c<='9')x=(x<<1)+(x<<3)+(c^48),c=getchar(); x=f?-x:x; } inline int mi(Re x,Re k){ Re s=1; while(k){ if(k&1)s=(LL)s*x%P; x=(LL)x*x%P,k>>=1; } return s; } struct CP{ int x,y;CP(Re X=0,Re Y=0){x=X,y=Y;} inline CP operator*(const CP &O)const{return CP(((LL)x*O.x%P+(LL)y*O.y%P*W%P)%P,((LL)x*O.y%P+(LL)y*O.x%P)%P);} inline CP operator*=(const CP &O){return *this=*this*O;} }; inline CP mi_(CP x,Re k){ CP s=CP(1,0); while(k){ if(k&1)s*=x; x*=x,k>>=1; } return s; } inline LL Sqrt(Re n){ if(!n)return 0;Re x; while(1){ x=rand()%P,W=((LL)x*x%P-n+P)%P; if(mi(W,(P-1)/2)==P-1)break; } return mi_(CP(x,1),(P+1)/2).x; } int main(){ // freopen("123.txt","r",stdin); in(T); while(T--){ in(n),in(P); if(mi(n,(P-1)/2)==P-1)puts("Hola!");//无解 else{ det=Sqrt(n); if(det)printf("%d %d\n",min(det,P-det),max(det,P-det));//两解 else printf("%d\n",det);//单解 } } }

10.【N 次剩余】

【模板】N 次剩余 [P5668]

#include <bits/stdc++.h> typedef long long LL; int A, B, mod; int pow(int x, int y, int mod = 0, int ans = 1) { if (mod) { for (; y; y >>= 1, x = (LL) x * x % mod) if (y & 1) ans = (LL) ans * x % mod; } else { for (; y; y >>= 1, x = x * x) if (y & 1) ans = ans * x; } return ans; } struct factor { int prime[20], expo[20], pk[20], tot; void factor_integer(int n) { tot = 0; for (int i = 2; i * i <= n; ++i) if (n % i == 0) { prime[tot] = i, expo[tot] = 0, pk[tot] = 1; do ++expo[tot], pk[tot] *= i; while ((n /= i) % i == 0); ++tot; } if (n > 1) prime[tot] = n, expo[tot] = 1, pk[tot++] = n; } int phi(int id) const { return pk[id] / prime[id] * (prime[id] - 1); } } mods, _p; int p_inverse(int x, int id) { assert(x % mods.prime[id] != 0); return pow(x, mods.phi(id) - 1, mods.pk[id]); } void exgcd(int a, int b, int &x, int &y) { if (!b) x = 1, y = 0; else exgcd(b, a % b, y, x), y -= a / b * x; } int inverse(int x, int mod) { assert(std::__gcd(x, mod) == 1); int ret, tmp; exgcd(x, mod, ret, tmp), ret %= mod; return ret + (ret >> 31 & mod); } std::vector<int> sol[20]; void solve_2(int id, int k) { int mod = 1 << k; if (k == 0) { sol[id].emplace_back(0); return; } else { solve_2(id, k - 1); std::vector<int> t; for (int s : sol[id]) { if (!((pow(s, A) ^ B) & mod - 1)) t.emplace_back(s); if (!((pow(s | 1 << k - 1, A) ^ B) & mod - 1)) t.emplace_back(s | 1 << k - 1); } std::swap(sol[id], t); } } int BSGS(int B, int g, int mod) { // g^x = B (mod M) => g^iL = B*g^j (mod M) : iL - j std::unordered_map<int, int> map; int L = std::ceil(std::sqrt(mod)), t = 1; for (int i = 1; i <= L; ++i) { t = (LL) t * g % mod; map[(LL) B * t % mod] = i; } int now = 1; for (int i = 1; i <= L; ++i) { now = (LL) now * t % mod; if (map.count(now)) return i * L - map[now]; } assert(0); } int find_primitive_root(int id) { int phi = mods.phi(id); _p.factor_integer(phi); auto check = [&] (int g) { for (int i = 0; i < _p.tot; ++i) if (pow(g, phi / _p.prime[i], mods.pk[id]) == 1) return 0; return 1; }; for (int g = 2; g < mods.pk[id]; ++g) if (check(g)) return g; assert(0); } void division(int id, int a, int b, int mod) { // ax = b (mod M) int M = mod, g = std::__gcd(std::__gcd(a, b), mod); a /= g, b /= g, mod /= g; if (std::__gcd(a, mod) > 1) return; int t = (LL) b * inverse(a, mod) % mod; for (; t < M; t += mod) sol[id].emplace_back(t); } void solve_p(int id, int B = ::B) { int p = mods.prime[id], e = mods.expo[id], mod = mods.pk[id]; if (B % mod == 0) { int q = pow(p, (e + A - 1) / A); for (int t = 0; t < mods.pk[id]; t += q) sol[id].emplace_back(t); } else if (B % p != 0) { int phi = mods.phi(id); int g = find_primitive_root(id), z = BSGS(B, g, mod); division(id, A, z, phi); for (int &x : sol[id]) x = pow(g, x, mod); } else { int q = 0; while (B % p == 0) B /= p, ++q; int pq = pow(p, q); if (q % A != 0) return; mods.expo[id] -= q, mods.pk[id] /= pq; solve_p(id, B); mods.expo[id] += q, mods.pk[id] *= pq; if (!sol[id].size()) return; int s = pow(p, q - q / A); int t = pow(p, q / A); int u = pow(p, e - q); std::vector<int> res; for (int y : sol[id]) { for (int i = 0; i < s; ++i) res.emplace_back((i * u + y) * t); } std::swap(sol[id], res); } } std::vector<int> allans; void dfs(int dep, int ans, int mod) { if (dep == mods.tot) {allans.emplace_back(ans); return;} int p = mods.pk[dep], k = p_inverse(mod % p, dep); for (int a : sol[dep]) { int nxt = (LL) (a - ans % p + p) * k % p * mod + ans; dfs(dep + 1, nxt, mod * p); } } void solve() { std::cin >> A >> mod >> B, mods.factor_integer(mod); allans.clear(); for (int i = mods.tot - 1; ~i; --i) { sol[i].clear(); mods.prime[i] == 2 ? solve_2(i, mods.expo[i]) : solve_p(i); if (!sol[i].size()) {return std::cout << 0 << '\n', void(0);} } dfs(0, 0, 1), std::sort(allans.begin(), allans.end()); std::cout << allans.size() << '\n'; for (int i : allans) std::cout << i << ' '; std::cout << '\n'; } int main() { std::ios::sync_with_stdio(0), std::cin.tie(0); int tc; std::cin >> tc; while (tc--) solve(); return 0; }

四：【类欧几里得算法】

【模板】类欧几里得算法 [P5170]

#include <bits/stdc++.h> using namespace std; #define Int register int #define mod 998244353ll #define int long long int inv2 = 499122177ll,inv6 = 166374059ll; struct Ans{int f,g,h;}; Ans Solve (int a,int b,int c,int n) { if (!a) { int f = (n + 1) * (b / c) % mod; int g = (n + 1) * (b / c) % mod * (b / c) % mod; int h = n * (n + 1) % mod * inv2 % mod * (b / c) % mod; return Ans {f % mod,g % mod,h % mod}; } else if (a >= c || b >= c) { Ans fucker = Solve (a % c,b % c,c,n); int F = fucker.f + n * (n + 1) / 2 % mod * (a / c) % mod + (n + 1) * (b / c) % mod; int G = fucker.g + 2 * (a / c) % mod * fucker.h % mod + 2 * (b / c) % mod * fucker.f + n % mod * (n + 1) % mod * (2 * n % mod + 1) % mod * inv6 % mod * (a / c) % mod * (a / c) % mod + n % mod * (n + 1) % mod * (a / c) % mod * (b / c) % mod + (n + 1) * (b / c) % mod * (b / c) % mod; int H = fucker.h + n % mod * (n + 1) % mod * (2 * n + 1) % mod * inv6 % mod * (a / c) % mod + n % mod * (n + 1) % mod * inv2 % mod * (b / c) % mod; return Ans {F % mod,G % mod,H % mod}; } else { int M = (a * n + b) / c; Ans fucker = Solve (c,c - b - 1,a,M - 1); int F = n * M % mod - fucker.f; int G = n * M % mod * (M + 1) % mod - 2 * fucker.h % mod + mod - 2 * fucker.f % mod + mod - F % mod; int H = (M * n % mod * (n + 1) % mod - fucker.g + mod - fucker.f) % mod * inv2 % mod; return Ans {F % mod,G % mod,H % mod}; } } int read () { int x = 0;char c = getchar();int f = 1; while (c < '0' || c > '9'){if (c == '-') f = -f;c = getchar();} while (c >= '0' && c <= '9'){x = (x << 3) + (x << 1) + c - '0';c = getchar();} return x * f; } void write (int x) { if (x < 0){x = -x;putchar ('-');} if (x > 9) write (x / 10); putchar (x % 10 + '0'); } signed main() { int times = read (); while (times --) { int n = read (),a = read (),b = read (),c = read (); Ans Putout = Solve (a,b,c,n); write ((Putout.f + mod) % mod),putchar (' '),write ((Putout.g + mod) % mod),putchar (' '),write ((Putout.h + mod) % mod),putchar ('\n'); } return 0; }

五：【各类反演及数论筛法】

1.【莫比乌斯函数(Mobius)】

(1).【埃氏筛】

#include<cstdio> const int N=1e7+3; int i,j,n,cnt,pan[N],miu[N]; inline void get_miu(){ for(i=1;i<=n;++i)miu[i]=1; for(i=2;i<=n;++i) if(!pan[i]){ miu[i]=-1; for(j=i<<1;j<=n;j+=i)pan[j]=1,miu[j]*=(j/i%i==0)?0:-1; } } int main(){ n=N; get_miu(); for(i=1;i<=n;++i)printf("%d: %d\n",i,miu[i]); }

(2).【线性筛】

#include<cstdio> const int N=1e7+3; int i,j,n,cnt,pri[N>>1],pan[N],miu[N]; inline void get_miu(){ pan[1]=1,miu[1]=1; for(i=2;i<=n;++i){ if(!pan[i])pri[++cnt]=i,miu[i]=-1; for(j=1;j<=cnt&&i*pri[j]<=n;++j){ pan[i*pri[j]]=1; if(i%pri[j])miu[i*pri[j]]=-miu[i]; else{miu[i*pri[j]]=0;break;} } } } int main(){ n=N; get_miu(); for(i=1;i<=n;++i)printf("%d: %d\n",i,miu[i]); }

2.【杜教筛】

(1).【map 记忆化】

【模板】 杜教筛（Sum）

#include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #include<map> #define Re register int #define LL long long using namespace std; const int N23=1664511+3,N=2147483647; int x,T,cnt,pan[N23],pri[N23],phi[N23],miu[N23]; int TO,Smiu[N23];LL Sphi[N23]; map<int,int>Smiu_;map<int,LL>Sphi_; inline void in(Re &x){ Re fu=0;x=0;char ch=getchar(); while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=fu?-x:x; } inline void get_(Re N){ miu[1]=phi[1]=pan[1]=1; for(Re i=2;i<=N;++i){ if(!pan[i])pri[++cnt]=i,miu[i]=-1,phi[i]=i-1; for(Re j=1;j<=cnt&&pri[j]<=N/i;++j){ pan[i*pri[j]]=1; if(i%pri[j])miu[i*pri[j]]=-miu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]]; else{miu[i*pri[j]]=0,phi[i*pri[j]]=phi[i]*pri[j];break;} } } for(Re i=1;i<=N;++i)Smiu[i]=Smiu[i-1]+miu[i],Sphi[i]=Sphi[i-1]+phi[i]; } inline LL get_Sphi(Re n){ if(n<=TO)return Sphi[n]; if(Sphi_[n])return Sphi_[n]; LL ans=(LL)n*(n+1)>>1; for(Re l=2,r;l<=n;l=r+1){ r=n/(n/l); ans-=(LL)(r-l+1)*get_Sphi(n/l); } return Sphi_[n]=ans; } inline int get_Smiu(Re n){ if(n<=TO)return Smiu[n]; if(Smiu_[n])return Smiu_[n]; Re ans=1; for(Re l=2,r;l<=n;l=r+1){ r=n/(n/l); ans-=(r-l+1)*get_Smiu(n/l); } return Smiu_[n]=ans; } int main(){ // freopen("123.txt","r",stdin); in(T),get_(TO=N23-3); while(T--)in(x),printf("%lld %d\n",get_Sphi(x),get_Smiu(x)); }

(2).【数组记忆化】

【模板】 杜教筛（Sum）[P4213]

#include<algorithm> #include<cstring> #include<cstdio> #include<cmath> #define Re register int #define LL long long using namespace std; const int N23=1664511+3,N13=1303,N=2147483647; int x,T,cnt,pan[N23],pri[N23],phi[N23],miu[N23]; int TO,vis1[N13],vis2[N13],Smiu[N23],Smiu_[N13]; LL Sphi[N23],Sphi_[N13]; inline void in(Re &x){ Re fu=0;x=0;char ch=getchar(); while(ch<'0'||ch>'9')fu|=ch=='-',ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=fu?-x:x; } inline void get_(Re N){ miu[1]=phi[1]=pan[1]=1; for(Re i=2;i<=N;++i){ if(!pan[i])pri[++cnt]=i,miu[i]=-1,phi[i]=i-1; for(Re j=1;j<=cnt&&pri[j]<=N/i;++j){ pan[i*pri[j]]=1; if(i%pri[j])miu[i*pri[j]]=-miu[i],phi[i*pri[j]]=phi[i]*phi[pri[j]]; else{miu[i*pri[j]]=0,phi[i*pri[j]]=phi[i]*pri[j];break;} } } for(Re i=1;i<=N;++i)Smiu[i]=Smiu[i-1]+miu[i],Sphi[i]=Sphi[i-1]+phi[i]; } inline LL get_Sphi(Re n){ if(n<=TO)return Sphi[n]; Re nn=N/n; if(vis1[nn])return Sphi_[nn]; LL ans=(LL)n*(n+1)>>1; for(Re l=2,r;l<=n;l=r+1){ r=n/(n/l); ans-=(LL)(r-l+1)*get_Sphi(n/l); } vis1[nn]=1; return Sphi_[nn]=ans; } inline int get_Smiu(Re n){ if(n<=TO)return Smiu[n]; Re nn=N/n; if(vis2[nn])return Smiu_[nn]; Re ans=1; for(Re l=2,r;l<=n;l=r+1){ r=n/(n/l); ans-=(r-l+1)*get_Smiu(n/l); } vis2[nn]=1; return Smiu_[nn]=ans; } int main(){ // freopen("123.txt","r",stdin); in(T),get_(TO=N23-3); while(T--){ in(x),printf("%lld %d\n",get_Sphi(x),get_Smiu(x)); memset(vis1,0,sizeof(vis1));//注意对于每次询问的n，n/i都不同 memset(vis2,0,sizeof(vis2));//所以要清空 } }

3.【最值反演 (Min-Max容斥)】

【模板】 Card Collector [Hdu4336]

#include<algorithm> #include<cstring> #include<cstdio> #define LD double #define LL long long #define Re register int using namespace std; const int N=23,M=1048576+3; int n,V,cnt[M];LD ans,p[N],Min[M]; inline void in(Re &x){ int f=0;x=0;char ch=getchar(); while(ch<'0'||ch>'9')f|=ch=='-',ch=getchar(); while(ch>='0'&&ch<='9')x=(x<<1)+(x<<3)+(ch^48),ch=getchar(); x=f?-x:x; } int main(){ // freopen("123.txt","r",stdin); while(~scanf("%d",&n)){ V=(1<<n)-1,ans=0; for(Re i=1;i<=n;++i)scanf("%lf",&p[i]); for(Re s=1;s<=V;++s){ Min[s]=0,cnt[s]=cnt[s>>1]+(s&1); for(Re i=1;i<=n;++i)if(s&(1<<i-1))Min[s]+=p[i]; Min[s]=1.0/Min[s]; } for(Re t=1;t<=V;++t)ans+=(cnt[t]&1)?Min[t]:-Min[t]; printf("%lf\n",ans); } }