推荐优秀的企业网站设计,线下销售怎么做推广,重庆网站推广专家,织梦网站定制文章目录 前言 回忆 题集12 杜教筛例题 前言
这里需要对莫反有一些基础。 不会的可以点这里
回忆 f ( n ) ∑ d ∣ n g ( d ) → g ( n ) ∑ d ∣ n f ( d ) μ ( n d ) f(n)\sum_{d|n}g(d)\rightarrow g(n)\sum_{d|n}f(d)\mu(\frac{n}{d}) f(n)∑d∣ng(d)→g(n)∑d∣n… 文章目录 前言 回忆 题集12 杜教筛例题 前言
这里需要对莫反有一些基础。 不会的可以点这里
回忆 f ( n ) ∑ d ∣ n g ( d ) → g ( n ) ∑ d ∣ n f ( d ) μ ( n d ) f(n)\sum_{d|n}g(d)\rightarrow g(n)\sum_{d|n}f(d)\mu(\frac{n}{d}) f(n)∑d∣ng(d)→g(n)∑d∣nf(d)μ(dn) ∑ d ∣ n μ ( d ) [ n 1 ] \sum_{d|n}\mu(d)[n1] ∑d∣nμ(d)[n1] ∑ i 1 n ⌊ n i ⌋ \sum_{i1}^n\left\lfloor\frac{n}{i}\right\rfloor ∑i1n⌊in⌋ 你应该知道怎么求 ∑ i 1 1 0 9 μ ( i ) \sum_{i1}^{10^9}\mu(i) ∑i1109μ(i) 你可能需要知道怎么求线性筛 μ ( i ) , φ ( i ) \mu(i),\varphi(i) μ(i),φ(i)一些数学能力
题集
1 ∏ i 1 n ∏ j 1 m gcd ( i , j ) \large\prod_{i1}^n\prod_{j1}^m\gcd(i,j) ∏i1n∏j1mgcd(i,j) ∏ d 1 d ∑ i 1 ∑ j 1 m [ gcd ( i , j ) d ] \prod_{d1}d^{\sum_{i1}\sum_{j1}^m[\gcd(i,j)d]} ∏d1d∑i1∑j1m[gcd(i,j)d] ∏ d 1 d ∑ k 1 min ( n , m ) d μ ( k ) n k d m k d \prod_{d1}d^{\sum_{k1}^\frac{\min(n,m)}{d}\mu(k)\frac{n}{kd}\frac{m}{kd}} ∏d1d∑k1dmin(n,m)μ(k)kdnkdm ∏ T 1 ( ∏ k ∣ T ( T k ) μ ( k ) ) n T m T \prod_{T1}(\prod_{k|T}(\frac{T}{k})^{\mu(k)})^{\frac{n}{T}\frac{m}{T}} ∏T1(∏k∣T(kT)μ(k))TnTm 令 f ( T ) ∏ k ∣ T ( T k ) μ ( k ) f(T)\prod_{k|T}(\frac{T}{k})^{\mu(k)} f(T)∏k∣T(kT)μ(k) 线性筛整出分块即可 Code:
#includebits/stdc.h
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
#define cou(i) coutfixedsetprecision(i)
using namespace std;
const int N1e71,mod1e97;
int t,n,m,k,ans,res;
unordered_mapint,intMu;
struct fy{int prv[N],cnt,mu[N],F[N];bool pr[N];int qmi(int x,int y){int res1;while(y0){if(y1)resres*x%mod;xx*x%mod,y1;}return res;}void ola(int x){pr[1]mu[1]F[1]1;for(int i2;ix;i){if(!pr[i])prv[cnt]i,mu[i]-1,F[i]i;for(int j1;jcnti*prv[j]x;j){int ui*prv[j];pr[u]1;if(i%prv[j]0){mu[u]0;F[u]F[i];break;}else{mu[u]-mu[i];F[u]1;}}}}void getsum(int x){F[0]1;for(int i1;ix;i){F[i]*F[i-1],F[i]%mod; }}int summu(int x){int res1;if(xN)return mu[x];if(Mu[x])return Mu[x];for(int l2,r;lx;lr1){rx/(x/l);res-(summu(x/l))*(r-l1);}Mu[x]res;return res;}int sumphi(int x){int res0;for(int l1,r;lx;lr1){rx/(x/l);res(summu(r)-summu(l-1))*(x/l)*(x/l);}return res;}
}A;
signed main(){IOS;A.ola(N-1);A.getsum(N-1);cint;while(t--){cinnm;int ans1ll;for(int l1,r;lmin(n,m);lr1){rmin(n/(n/l),m/(m/l));int resA.F[r]*A.qmi(A.F[l-1],mod-2)%mod;ansans*A.qmi(res,(n/l)*(m/l))%mod;}coutans\n;}return 0;
}经验 1 2 3
2
Link 暴力推式子。 关键: gcd ( i j , j k , k i ) gcd ( i , j ) gcd ( j , k ) gcd ( k , i ) gcd ( i , j , k ) \large{\gcd(ij,jk,ki)\frac{\gcd(i,j)\gcd(j,k)\gcd(k,i)}{\gcd(i,j,k)}} gcd(ij,jk,ki)gcd(i,j,k)gcd(i,j)gcd(j,k)gcd(k,i) 然后可得原式于神之怒加强版或这里 好像这黑题有那么一点点水啊 Code:
#includebits/stdc.h
#define int long long
#define IOS ios::sync_with_stdio(false),cin.tie(NULL),cout.tie(NULL)
using namespace std;
const int N2e71,mod1e97;
int t,n,m,p,k;
struct fy{int prv[N],cnt,g[N],s[N];bool pr[N];inline int qmi(int x,int y){int res1;while(y0){if(y1)resres*x%mod;xx*x%mod,y1;}return res;}void ola(int x){pr[1]g[1]1;for(int i2;ix;i){if(!pr[i])prv[cnt]i,g[i](qmi(i,k)-1mod)%mod;for(int j1;jcnti*prv[j]x;j){int ui*prv[j];pr[u]1;if(i%prv[j]0){g[u]g[i]*qmi(prv[j],k)%mod;break;}else{g[u]g[i]*g[prv[j]]%mod;}}}}void getsum(int x){for(int i1;ix;i)g[i](g[i]g[i-1])%mod;}
}A;
signed main(){IOS;k2;cint;A.ola(N-1);A.getsum(N-1);while(t--){cinnmp;int ans0,res0;for(int l1,r;lmin(n,m);lr1){rmin(n/(n/l),m/(m/l));res(n/l)*(m/l)%mod*((A.g[r]-A.g[l-1]mod)%mod)%mod;res%mod;}ansres*p;ans%mod;res0;for(int l1,r;lmin(m,p);lr1){rmin(m/(m/l),p/(p/l));res(m/l)*(p/l)%mod*((A.g[r]-A.g[l-1]mod)%mod)%mod;res%mod;}ansres*n;ans%mod;res0;for(int l1,r;lmin(p,n);lr1){rmin(p/(p/l),n/(n/l));res(p/l)*(n/l)%mod*((A.g[r]-A.g[l-1]mod)%mod)%mod;res%mod;}ansres*m;ans%mod;coutans\n;}return 0;
}杜教筛
来自 OI-wiki的资料
这里直达 这里直达OI-wiki 例题
给定一个正整数求 a n s 1 ∑ i 1 n φ ( i ) , a n s 2 ∑ i 1 n μ ( i ) ans_1\sum_{i1}^n\varphi(i),ans_2\sum_{i1}^n \mu(i) ans1∑i1nφ(i),ans2∑i1nμ(i) 输入的第一行为一个整数表示数据组数 T T T。 接下来 T T T 行每行一个整数 n n n表示一组询问。 对于每组询问输出一行两个整数分别代表 a n s 1 ans_1 ans1 和 a n s 2 ans_2 ans2。 对于全部的测试点保证 1 ≤ T ≤ 10 1 \leq T \leq 10 1≤T≤10 1 ≤ n 2 31 1 \leq n \lt 2^{31} 1≤n231。 考虑使用杜教筛。 设 S 1 ( n ) ∑ i 1 n μ ( i ) S_1(n)\sum_{i1}^n\mu(i) S1(n)∑i1nμ(i) 那样我们就完成了两个最简单的例题了 Code:
#includebits/stdc.h
#define int __int128
using namespace std;
const int N2e61,mod1e97;
int t,n,m,k;
void write(int x){if(x0)putchar(-),x-x;if(x10)write((int)(x/10));char o0x%10;putchar(o);
}
void read(int x){x0;int y1;char cgetchar();while(c9||c0){if(c-){y-1;break;}cgetchar();}while(c9c0)xx*10c-0,cgetchar();x*y;
}
mapint,intMu,Phi;
struct fy{int prv[N],cnt,phi[N],mu[N];bool pr[N];void ola(int x){pr[1]mu[1]1;for(int i2;ix;i){if(!pr[i])prv[cnt]i,mu[i]-1;for(int j1;jcnti*prv[j]x;j){int ui*prv[j];pr[u]1;if(i%prv[j]0){mu[u]0;break;}else{mu[u]-mu[i];}}}}void getsumF(int x){for(int i1;ix;i)mu[i]mu[i-1];}int summu(int x){int res1;if(xN)return mu[x];if(Mu[x])return Mu[x];for(int l2,r;lx;lr1){rx/(x/l);res-(summu(x/l))*(r-l1);}Mu[x]res;return res;}int sumphi(int x){int res0;for(int l1,r;lx;lr1){rx/(x/l);res(summu(r)-summu(l-1))*(n/l)*(n/l);}return res;}
}A;
signed main(){A.ola(N-1);A.getsumF(N-1);read(t);while(t--){read(n);write((A.sumphi(n)-1)/21);putchar( );write(A.summu(n));putchar(\n);}return 0;
}
//此代码有一点瑕疵但确实可以过模板题
