欧拉函数+反演——2019hdu多校6588

清疚 2023-10-11 09:16 5阅读 0赞

\\\[ 求\\sum\_\{i=1\}^\{n\}(\\sqrt\[3\]i,i)\\\\ 首先转化一下这个式子，考虑对于i\\in\[j^3,(j+1)^3-1\]，\\sqrt\[3\]i=j\\\\ 所以可以枚举所有j，然后对i\\in\[j^3,(j+1)^3-1\]区间的(i,j)求和即可 那么我们把n分成两部分，分别求和：\\\\ \\sum\_\{i=1\}^\{n\}(\\sqrt\[3\]i,i)=\\sum\_\{i=\{\\lfloor \\sqrt\[3\]n\\rfloor\}^3\}^\{n\}(\\sqrt\[3\]n,n) +\\sum\_\{j=1\}^\{\\sqrt\[3\]n-1\}\\sum\_\{i=j^3\}^\{(j+1)^3-1\}(i,j)\\\\ \\\]

\\\[ 先来看前面一个合式\\sum\_\{i=\{\\lfloor \\sqrt\[3\]n\\rfloor\}^3\}^\{n\}(\\sqrt\[3\]n,i)，直接用欧拉替换式\\\\ 原式=\\sum\_\{i=\{\\lfloor \\sqrt\[3\]n\\rfloor\}^3\}^\{n\}\\ \\sum\_\{d|i,d|\{\\lfloor \\sqrt\[3\]n\\rfloor\}\}\\varphi(d) =\\sum\_\{d|\{\\lfloor \\sqrt\[3\]n\\rfloor\}\}\\varphi(d)\\big(n/d-(\\lfloor \\sqrt\[3\]n\\rfloor-1)/d \\big)\\\\ \{\\lfloor \\sqrt\[3\]n\\rfloor\}因子是不多的，只有\\sqrt\[6\]n个，所以复杂度也是这个 \\\]

\\\[ 再看后面一个合式，我们可以将其转化后用反演来快速求和\\\\ \\sum\_\{j=1\}^\{\\sqrt\[3\]n-1\}\\sum\_\{i=j^3\}^\{(j+1)^3-1\}(i,j) =\\sum\_\{j=1\}^\{\\sqrt\[3\]n-1\}\\bigg(\\sum\_\{i=1\}^\{(j+1)^3-1\}(i,j)-\\sum\_\{i=1\}^\{j^3-1\}(i,j) \\bigg)\\\\ 现在来求\\sum\_\{j=1\}^\{\\sqrt\[3\]n-1\}\\sum\_\{i=1\}^\{f(j)\}(i,j),其实可以把(i,j)展开做，但是考虑到欧拉替换\\\\ 原式=\\sum\_\{j=1\}^\{\\sqrt\[3\]n-1\}\\sum\_\{i=1\}^\{f(j)\}\\sum\_\{d|i,d|j\}\\varphi(d) =\\sum\_\{j=1\}^\{\\sqrt\[3\]n-1\}\\sum\_\{d|j\}\\varphi(d)\\frac\{f(j)\}\{d\} \\\\ 注意因为i的上界是和j有关的，所以切换枚举次序时只能把d切换到i前，不能切换到j前，否则无法正确求出\\varphi(d)出现次数\\\\ 原式=\\sum\_\{j=1\}^\{\\sqrt\[3\]n-1\}\\sum\_\{d|j\}\\varphi(d)\\bigg(\\lfloor \\frac\{(j+1)^3-1\}\{d\}\\rfloor-\\lfloor \\frac\{j^3-1\}\{d\}\\rfloor \\bigg) \\ 显然有j=kd，所以不妨外层枚举d\\\\ 原式=\\sum\_\{d=1\}^\{N=\\sqrt\[3\]n-1\}\\varphi(d)\\sum\_\{k=1\}^\{\\frac\{N\}\{d\}\}(3k^2d+3k+1) =\\sum\_\{d=1\}^\{N=\\sqrt\[3\]n-1\}\\varphi(d)(3d\\sum\_\{k=1\}^\{\\frac\{N\}\{d\}\}k^2+3\\sum\_\{k=1\}^\{\\frac\{N\}\{d\}\}k+\\frac\{N\}\{d\}) \\\\ 到此为止，我们可以预处理\[1,1e7\]范围的k^2,k的前缀和，\\varphi(i)的值,就可以O(1)求每个d的值 \\\]

#include <bits/stdc++.h> const int N=1e7,XN=N+11,P=998244353; int Add(int x,int const &y) {return (x+=y)>=P?x-P:x;} int Minus(int x,int const &y) {return (x-=y)<0?x+P:x;} int Mul(long long x,int const &y) {return x*y%P;} int prime[XN],phi[XN],pcnt; void Prep() { static bool notPrime[XN]; phi[1]=1; for(int i=2;i<=N;++i) { if(!notPrime[i]) { prime[++pcnt]=i; phi[i]=i-1; } for(int j=1;j<=pcnt && i*prime[j]<=N;++j) { notPrime[i*prime[j]]=1; if(i%prime[j]==0) { phi[i*prime[j]]=phi[i]*prime[j]; break; } else phi[i*prime[j]]=phi[i]*phi[prime[j]]; } } } int Sum1(long long x) {return x*(x+1)/2%P;} int Sum2(long long x) {return (x*(x+1))%(6ll*P)*(2*x+1)/6%P;} int Calc(int a,__int128 L,__int128 R) { int res=0; for(int d=1;1LL*d*d<=a;++d) if(a%d==0) { res=Add(res,Mul((R/d-L/d)%P,phi[d])); if(a!=d*d) res=Add(res,Mul((R/(a/d)-L/(a/d))%P,phi[a/d])); } return res; } int main() { Prep();int T;fin>>T; while(T--) { __int128 n;fin>>n; if(n<=7) {fout<<n<<'\n';} else { int r;for(r=1;(__int128)(r+2)*(r+2)*(r+2)-1<=n;++r); int Ans=Calc(r+1,(__int128)(r+1)*(r+1)*(r+1)-1,n); for(int T=1;T<=r;++T) Ans=Add(Ans,Mul(phi[T],Add(Add(Mul(3*T,Sum2(r/T)),Mul(3,Sum1(r/T))),r/T))); fout<<Ans<<'\n'; } } }

转载于:https://www.cnblogs.com/zsben991126/p/11365423.html