洛咕【P1891】疯狂LCM & 三倍经验

亦凉 2021-11-14 11:42 306阅读 0赞

经验给掉先：

[经验\*1][1]

[经验\*2][2]

[经验\*3][3]

这里给个跑得比较慢的 \$n \\sqrt n\$ 预处理然后 \$O(1)\$ 回答询问的做法

# 式子 #

首先我们推柿子：

\\\[\\begin\{aligned\}ANS&= \\sum\_\{i=1\}^n lcm(i,n)\\\\ &=\\sum\_\{i=1\}^n \{i\* n\\over (i,n)\} \\\\&= n\\sum\_\{i=1\}^n \{i\\over (i,n)\} \\\\&=n\\sum\_\{d|n\} \\sum\_\{i=1\}^\{n/d\} i \[(i,n/d)=1\] \\\\&=n\\sum\_\{d|n\} \{\\Big(\\varphi(\{n\\over d\})+\\epsilon(\{n\\over d\}) \\Big)\{n\\over d\} \\over 2\} \\\\&=n\\sum\_\{d|n\} \{\\Big(\\varphi(d)+\\epsilon(d) \\Big)\{d\} \\over 2\} \\end\{aligned\}\\\]

大概就是这样的

解释一下 \$\\varphi\$ 怎么出来的，我们可以看出第四行的式子如果没有 i 的话后面那玩意儿就是 $\\varphi $ ，然后我们考虑互质的对称性，即 当 \$i\\perp n\$ 时， \$(n-i)\\perp n\$ ， 所以他们一一对应，并且相加为 n ，只有 \$n=1\$ 的情况有点特别，那么咱用 单位元凑就好咯，还有除以 2 别忘了，一一对应相加后数量除以 2

# 处理 #

咱考虑欧拉筛一遍就能搞出这个 \$\\varphi(i)\* i\$ ，那么重要的就是累加了...

咱考虑枚举每个 i ，然后再枚举一个数 j ，令 \$i\* j \\le Max\_n\$ ，然后咱用 \$\\big(\\varphi(i)+\\epsilon(i)\\big)i \\over 2\$ 给 $i\* j $ 累加上去就好了

这样的复杂度是多少呢？

咱倒过来考虑，就是对于 1~n 每个数把它的因数全都计算了一遍答案，那么一个数 n 拥有的因数个数是 \$O(\\sqrt n)\$ 级别的，咱积分

\\\[\\int\_0^n \\sqrt x dx= \{2\\over 3\} n^\{3\\over 2\} =O(n\\sqrt n) \\\]

讲道理感性理解一下就是 n 带根号啦...

# Code #

//by Judge #include<cmath> #include<cstdio> #include<cstring> #include<iostream> #define Rg register #define fp(i,a,b) for(Rg int i=(a),I=(b)+1;i<I;++i) #define ll long long using namespace std; const int M=1e6+3; typedef ll arr[M]; #ifndef Judge #define getchar() (p1==p2&&(p2=(p1=buf)+fread(buf,1,1<<21,stdin),p1==p2)?EOF:*p1++) #endif char buf[1<<21],*p1=buf,*p2=buf; inline ll read(){ ll x=0,f=1; char c=getchar(); for(;!isdigit(c);c=getchar()) if(c=='-') f=-1; for(;isdigit(c);c=getchar()) x=x*10+c-'0'; return x*f; } char sr[1<<21],z[20];int CCF=-1,Z; inline void Ot(){fwrite(sr,1,CCF+1,stdout),CCF=-1;} inline void print(ll x,char chr='\n'){ if(CCF>1<<20)Ot();if(x<0)sr[++CCF]=45,x=-x; while(z[++Z]=x%10+48,x/=10); while(sr[++CCF]=z[Z],--Z);sr[++CCF]=chr; } ll n,cnt; arr v,p,phi,ans; inline void prp(int n){ v[1]=1,phi[1]=1; fp(i,2,n){ if(!v[i]) p[++cnt]=i,phi[i]=i-1; for(Rg int j=1;j<=cnt&&1ll*i*p[j]<=n;++j){ v[i*p[j]]=1; if(!(i%p[j])){ phi[i*p[j]]=phi[i]*p[j]; break; } phi[i*p[j]]=phi[i]*(p[j]-1); } phi[i]*=i,phi[i]/=2; } fp(i,1,n) fp(j,1,n/i) ans[i*j]+=phi[i]; } int main(){ int T=read(); prp(1e6); while(T--) n=read(),print(ans[n]*n); return Ot(),0; }

转载于:https://www.cnblogs.com/Judge/p/11268142.html

[1]: https://www.luogu.org/problem/P1891
[2]: https://www.luogu.org/problem/SP5971
[3]: https://www.lydsy.com/JudgeOnline/problem.php?id=2226