相关链接
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=2986
神犇题解:http://www.acmtime.com/?p=527
首先安利两篇Blog:
http://blog.csdn.net/skywalkert/article/details/50500009
http://www.cnblogs.com/joyouth/p/5517734.html
自己对于杜教筛的理解就是下面这个式子:
\(\left\{ {\begin{array}{*{20}{l}}
{f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\
{(\varphi \times I)(x) = id}\\
{g(n) = \sum\limits_{i = 1}^n {id(i)} }
\end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})} \)
题目传送门:http://acm.hdu.edu.cn/showproblem.php?pid=5608
这题,看一眼体面就应该知道是杜教筛吧?
唯一的问题就是求\(\sum\limits_{i = 1}^n {{i^2}} \)
然后就不会了,去问问数竞的大爷,被告知:\(\sum\limits_{i = 1}^n {{i^2}} = \frac{{n \cdot (n + 1) \cdot (2n + 1)}}{6}\)是一个基本公式
至于证明,貌似最清真的还是数学归纳法吧:
设i=1,k=2,不难得出此时原式成立
令k’=k+1则有:\(\sum\limits_{i = 1}^{k’} {{i^2} = \sum\limits_{i = 1}^k {{i^2} + {{(k + 1)}^2} = \frac{{(k + 1) \cdot (k + 2) \cdot (2k + 3)}}{6} = \frac{{k’ \cdot (k’ + 1) \cdot (2k’ + 1)}}{6}} } \)
即命题对于\(\forall k\)都成立
题目传送门:http://www.lydsy.com/JudgeOnline/problem.php?id=3944
好像没有什么特别的
但讲道理,下面是map,上面是unordered_map
讲道理啊!这™复杂度都不一样啊!
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5000000+9; const int MX = 5000000; int mu[N],cnt,pri[N]; bool vis[N]; LL phi[N]; map<int,int> MU; map<int,LL> PHI; inline int read(){ char c=getchar(); int ret=0,f=1; while (c<'0'||c>'9') {if(c=='-')f=-1;c=getchar();} while (c<='9'&&c>='0') {ret=ret*10+c-'0';c=getchar();} return ret*f; } inline void prework(){ mu[1] = phi[1] = 1; for (int i=2;i<=MX;i++) { if (!vis[i]) pri[++cnt] = i, mu[i] = -1, phi[i] = i-1; for (int j=1,w;j<=cnt && pri[j]*i<=MX;j++) { vis[i*pri[j]] = 1; w = pri[j]*i; if (i%pri[j]) mu[w] = -mu[i], phi[w] = phi[i]*(pri[j]-1); else {phi[w] = phi[i]*pri[j]; break;} } } for (int i=1;i<=MX;i++) mu[i] += mu[i-1], phi[i] += phi[i-1]; } inline int solve_mu(int w) { if (w <= MX) return mu[w]; else if (MU[w]) return MU[w]; else { int ret = 1; for (LL i=2,tmp;i<=w;i=tmp+1) { tmp = w / (w / i); ret -= solve_mu(w/tmp)*(tmp-i+1); } MU[w] = ret; return ret; } } int LL solve_phi(int w) { if (w <= MX) return phi[w]; else if (PHI[w]) return PHI[w]; else { LL ret = w * ((LL)w+1) / 2; for (LL i=2,tmp;i<=w;i=tmp+1) { tmp = w / (w/i); ret -= solve_phi(w/tmp)*(tmp-i+1); } PHI[w] = ret; return ret; } } int main(){ prework(); for (int t=read(),w;t;t--) w = read(), printf("%lld %d\n",solve_phi(w),solve_mu(w)); return 0; }
题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1244
这个题目,貌似和【51NOD_1239】欧拉函数之和基本一样?
#include<bits/stdc++.h> #define LL long long using namespace std; const int N = 5000000+9; const int MX = 5000000; int mu[N],cnt,pri[N]; bool vis[N]; unordered_map<LL,LL> M; inline int prework(){ mu[1] = 1; for (int i=2;i<=MX;i++) { if (!vis[i]) pri[++cnt] = i, mu[i] = -1; for (int j=1;j<=cnt && pri[j]*i<=MX;j++) { vis[i*pri[j]] = 1; if (i%pri[j]) mu[i*pri[j]] = -mu[i]; else break; } } for (int i=1;i<=MX;i++) mu[i] += mu[i-1]; } inline LL solve(LL w) { if (w <= MX) return mu[w]; else if (M[w]) return M[w]; else { LL ret = 1; for (LL i=2,tmp;i<=w;i=tmp+1) { tmp = w / (w / i); ret -= solve(w/tmp)*(tmp-i+1); } M[w] = ret; return ret; } } int main(){ prework(); LL a,b; cin>>a>>b; printf("%d\n",solve(b)-solve(a-1)); return 0; }
题目传送门:http://www.51nod.com/onlineJudge/questionCode.html#!problemId=1239
传说中的杜教筛!虽然网上式子很多了,但还是推一推吧!
总体思路:
\(\left\{ {\begin{array}{*{20}{l}}
{f(n) = \sum\limits_{i = 1}^n {\varphi (i)} }\\
{(\varphi \times I)(x) = id}\\
{g(n) = \sum\limits_{i = 1}^n {id(i)} }
\end{array}} \right. \Rightarrow f(n) = g(n) – \sum\limits_{i = {\rm{2}}}^n {f(\frac{n}{i})} \)
至于杜教筛的顺逆推问题,感觉只能凑
不过想一想,能凑的也不过mu,phi这些
#include<bits/stdc++.h> #define LL long long using namespace std; const int MOD = 1000000007; const int REV = 500000004; const int MX = 5000000; const int N = MX + 9; unordered_map<LL,int> M; int phi[N],pri[N],tot; bool vis[N]; inline LL read(){ char c=getchar(); LL ret=0; while (c<'0'||c>'9') c=getchar(); while (c<='9'&&c>='0') ret=ret*10+c-'0',c=getchar(); return ret; } inline void prework(){ phi[1] = 1; for (int i=2;i<=MX;i++) { if (!vis[i]) pri[++tot] = i, phi[i] = i - 1; for (int j=1;j<=tot && pri[j]*i<=MX;j++) { vis[pri[j]*i] = 1; if (i%pri[j]) phi[i*pri[j]] = phi[i]*(pri[j]-1); else {phi[i*pri[j]] = phi[i]*pri[j]; break;} } }for (int i=1;i<=MX;i++) phi[i] += phi[i-1], phi[i] %= MOD; } int solve(LL w) { if (w <= MX) return phi[w]; else if (M[w]) return M[w]; else { int ret = ((w%MOD)*((w+1)%MOD)%MOD)*REV%MOD; for (LL i=2,tmp;i<=w;i=tmp+1) { tmp = w / (w/i); ret %= MOD; ret -= (LL)solve(w/tmp)*(tmp-i+1) % MOD; } ((ret%=MOD)+=MOD)%=MOD; M[w] = ret; return ret; } } int main(){ prework(); printf("%d\n",solve(read())); return 0; }