首先推一波式子可以得到：
$LHS=\sum_{T=1}^{n}\left\lfloor\frac{n}{T}\right\rfloor\left\lfloor\frac{n}{T}\right\rfloor\sum_{d|T}\mu(d)\phi(\frac{T}{d})$
设$g(T)=\sum_{d|T}\mu(d)\phi(\frac{T}{d})=\mu\times\phi$，所以$g(T)$是积性函数，考虑线筛
（1）$g(1)=\mu(1)\phi(1)=1$
（2）当$i$为质数时，$g(i)=\mu(1)\phi(i)+\mu(i)\phi(1)=i-2$
（3）当$i\%prime[j] \neq 0$时，$g(i\times prime[j])=g(i)\times g(prime[j])$
（4）当$i\%prime[j]=0$时，下面重点讨论（下式中$prime[j]$简写为$p_j$）：
设$i=p_j^a \prod p_c^{q_c}$，根据$g(i)$的积性有
$g(i)=g(p_j^a)\prod g(p_c^{q_c})$
$g(i\times p_j)=g(p_j^{a+1})\prod g(p_c^{q_c})$
故有$\frac{g(i\times p_j)}{g(i)}=\frac{g(p_j^{a+1})}{g(p_j^a)}=\frac{\mu(1)\phi(p_j^{a+1})+\mu(p_j)\phi(p_j^a)}{\mu(1)\phi(p_j^{a})+\mu(p_j)\phi(p_j^{a-1})}=\frac{\phi(p_j^{a+1})-\phi(p_j^a)}{\phi(p_j^a)-\phi(p_j^{a-1})}$
①当$a>1$时，$LHS=\frac{p_j^{a+1}\times \frac{p_j-1}{p_j}-p_j^{a}\times \frac{p_j-1}{p_j}}{p_j^{a}\times \frac{p_j-1}{p_j}-p_j^{a-1}\times \frac{p_j-1}{p_j}}=p_j$，即$g(i\times primej)=prime[j]\times g(i)$
②当$a=1$时，$LHS=\frac{\phi(p_j^2)-\phi(p_j)}{\phi(p_j)-\phi(1)}=\frac{(p_j-1)^2}{p_j-2}$
注意到这个式子和①中的不一样，这是因为按照定义式计算欧拉函数值得话$\phi(1)=0$，但实际上$\phi(1)=1$
由于分母变成了$p_j-2$导致$p_j=2$的情况无法处理，我们考虑另一种思路：
显然根据积性有$g(i\times p_j)=g(\frac{i}{p_j})\times g(p_j^2)=g(\frac{i}{p_j})\times (\mu(1)\phi(p_j^2)+\mu(p_j)\phi(p_j))=g(\frac{i}{p_j})\times (p_j-1)^2$
这样就完美解决了
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
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 10000100 using namespace std; typedef long long ll; int cnt,prime[MAXN/10],check[MAXN];ll g[MAXN]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } void Init(){ int N=10000000; g[1]=1; for(int i=2;i<=N;++i){ if(!check[i]) prime[++cnt]=i,g[i]=i-2; for(int j=1;j<=cnt&&prime[j]*i<=N;++j){ check[prime[j]*i]=1; if(i%prime[j]==0){ if((i/prime[j])%prime[j]==0) g[prime[j]*i]=g[i]*prime[j]; else g[prime[j]*i]=g[i/prime[j]]*(prime[j]-1)*(prime[j]-1); break; } else g[prime[j]*i]=g[i]*g[prime[j]]; } } for(int i=1;i<=N;++i) g[i]+=g[i-1]; } void solve(){ int n=read(); ll ans=0; for(int i=1,last;i<=n;i=last+1){ last=(n/(n/i)); ans+=1LL*(n/i)*(n/i)*(g[last]-g[i-1]); } printf("%lld\n",ans); } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); Init(); int T=read(); while(T--) solve(); return 0; }
|
然而看了题解，我才发现我SB了
题上给的两个求和号上界都是$n$不是白给的，按照仪仗队那道题做就行了
$LHS=\sum_{k=1}^{n}\phi(k)\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}\sum_{j=1}^{\left\lfloor\frac{n}{k}\right\rfloor}[gcd(i,j)==1]$
$=\sum_{k=1}^{n}\phi(k)[\sum_{i=1}^{\left\lfloor\frac{n}{k}\right\rfloor}2\phi(i)-1]$
$=2\sum_{k=1}^{n}\phi(k)Sum(\left\lfloor\frac{n}{k}\right\rfloor)-sum(n)$（其中$sum$是$\phi$的前缀和）
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
| #include<bits/stdc++.h> #define FILE "read" #define MAXN 10000010 using namespace std; typedef long long ll; int cnt,prime[MAXN/10],check[MAXN];ll phi[MAXN]; inline int read(){ int x=0,f=1; char ch=getchar(); while(ch>'9'||ch<'0') {if(ch=='-') f=-1; ch=getchar();} while(ch>='0'&&ch<='9') {x=x*10+ch-'0'; ch=getchar();} return x*f; } void Init(){ int N=10000000; phi[1]=1; for(int i=2;i<=N;++i){ if(!check[i]) prime[++cnt]=i,phi[i]=i-1; for(int j=1;j<=cnt&&prime[j]*i<=N;++j){ check[prime[j]*i]=1; if(i%prime[j]==0) {phi[prime[j]*i]=phi[i]*prime[j]; break;} else phi[prime[j]*i]=phi[i]*phi[prime[j]]; } } for(int i=1;i<=N;++i) phi[i]+=phi[i-1]; } void solve(){ int n=read(); ll ans=0; for(int i=1,last;i<=n;i=last+1){ last=(n/(n/i)); cadd(ans,phi[n/i]*(phi[last]-phi[i-1]); } printf("%lld\n",ans*2-phi[n]); } int main(){ freopen(FILE".in","r",stdin); freopen(FILE".out","w",stdout); Init(); int T=read(); while(T--) solve(); return 0; }
|