题目链接:http://www.lydsy.com/JudgeOnline/problem.php?id=3944
题意:欧拉函数,莫比乌斯函数前缀和,\(n\leq 2^{31}-1\)
人生中的第一次杜教筛= =
n 很大,显然不能线性筛了。现在只考虑莫比乌斯函数的前缀和,欧拉函数同理。
构造这么几个函数:
$$g(n)=\sum_{i=1}^{n}\mu (i)$$
$$f(n)=\sum_{d|n}^{ }\mu (d)$$
$$F(n)=\sum_{i=1}^{n}f(i)$$
很显然,\(F(n)=1+0+0+...+0=1\)。
另外,\(F(n)=\sum_{i=1}^{n}\mu (i)\cdot \left \lfloor \frac{n}{i} \right \rfloor=\sum_{i=1}^{n} g(\left \lfloor \frac{n}{i} \right \rfloor)\)
这是为什么呢,想想就知道,比如\(\mu (1)\) 出现了\(n\) 次,在每个\(g(\frac{n}{i})\) 中都出现了,\(\mu (2)\) 只出现了\(\left \lfloor \frac{n}{2} \right \rfloor\) 次,仅在\(\left \lfloor \frac{n}{i} \right \rfloor\geq 2\) 的\(g\) 中出现了,以此类推。
所以\(\sum_{i=1}^{n}g(\left \lfloor \frac{n}{i} \right \rfloor)=1\),那么\(g(n)=1-\sum_{i=2}^{n}g(\left \lfloor \frac{n}{i} \right \rfloor)\)
这玩意递归求解即可,但是直接上会 T。我们可以预处理出一些 n 比较小的前缀和,可以证明的是,预处理到\(n^{\frac{2}{3}}\) 处是最优的。
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 |
#include <map> #include <cmath> #include <queue> #include <cstdio> #include <iomanip> #include <cstdlib> #include <cstring> #include <iostream> #include <algorithm> #define N 5000000 #define ll long long using namespace std; inline ll read() { ll x=0,f=1;char ch=getchar(); while(ch<'0'||ch>'9'){if(ch=='-')f=-1;ch=getchar();} while(ch>='0'&&ch<='9'){x=x*10+ch-'0';ch=getchar();} return x*f; } int mu[N+10],pri[N+10],cnt; ll phi[N+10],n; bool pd[N+10]; map<int,ll> ans_mu,ans_phi; map<int,bool> have_mu; int get_mu(ll x) { if(x<=N)return mu[x]; if(ans_mu[x])return ans_mu[x]; int tmp=1; for(int i=2,j=0;i<=x;i=j+1) { j=x/(x/i); tmp-=(j-i+1)*get_mu(x/i); if (j==x) break; } ans_mu[x]=tmp; return tmp; } ll get_phi(ll x) { if(x<=N)return phi[x]; if(ans_phi[x])return ans_phi[x]; ll tmp=(ll)x*(x+1)/2; for(int i=2,j=0;i<=x;i=j+1) { j=x/(x/i); tmp-=(ll)(j-i+1)*get_phi(x/i); if (j==x) break; } ans_phi[x]=tmp; return tmp; } void pre() { mu[1]=phi[1]=1; for(int i=2;i<=N;i++) { if(!pd[i])mu[i]=-1,pri[++cnt]=i,phi[i]=i-1; for(int j=1;i*pri[j]<=N&&j<=cnt;j++) { pd[i*pri[j]]=1; if(i%pri[j]==0) { mu[i*pri[j]]=0; phi[i*pri[j]]=phi[i]*pri[j]; break ; } mu[i*pri[j]]=-mu[i]; phi[i*pri[j]]=phi[i]*(pri[j]-1); } } for(int i=1;i<=N;i++) mu[i]+=mu[i-1],phi[i]+=phi[i-1]; } int T; int main() { T=read();pre(); while(T--) { n=read(); printf("%lld %d\n",get_phi(n),get_mu(n)); } } |
Comments | NOTHING