OTZ 又被吊打了。。。我当初学的都去哪了？？？
思路：反演套路？
提交：(1)次
题解：
求(sum_{i=1}^{n}sum_{j=1}^{n}varphi(gcd(varphi(i),varphi(j))))
设(c[i]=sum_{j=1}^n[varphi(j)==i])
有：
(sum_{i=1}^{n}sum_{j=1}^{n}varphi(gcd(i,j))*c[i]*c[j])
欧拉反演一下，把(gcd)扔出来
(sum_{i=1}^{n}sum_{j=1}^{n}sum_{d|gcd(i,j)}varphi(d)*c[i]*c[j]*[gcd(i,j)==d])
(sum_{d=1}^{n}varphi(d) sum_{i=1}^{lfloor frac{n}{d} floor} sum_{j=1}^{lfloor frac{n}{d} floor} c[i*d]* c[j*d]* [gcd(i,j)==1])
(sum_{d=1}^{n}varphi(d) sum_{i=1}^{lfloor frac{n}{d} floor}c[i*d] sum_{j=1}^{lfloor frac{n}{d} floor}c[j*d] [gcd(i,j)==1])
(sum_{d=1}^{n}varphi(d) sum_{i=1}^{lfloor frac{n}{d} floor}c[i*d] sum_{j=1}^{lfloor frac{n}{d} floor}c[j*d] sum_{k|gcd(i,j)} mu(k))
(sum_{d=1}^{n}varphi(d) sum_{k=1}^{lfloor frac{n}{d} floor} mu(k) sum_{i=1}^{lfloor frac{n}{d*k} floor}c[i*d*k] sum_{j=1}^{lfloor frac{n}{d*k} floor}c[j*d*k])
设(s[i]=sum_{j=1}^{lfloor frac{n}{i} floor} c[i*j]),注意到(s[i])可以在(O(nlogn))计算出来
(sum_{d=1}^{n} varphi(d) sum_{k=1}^{lfloor frac{n}{d} floor} mu(k) s[d*k]^2)
交换一下(d)与(k)，可以优化枚举（见代码）
(sum_{d=1}^{n} mu(d) sum_{k=1}^{lfloor frac{n}{d} floor} varphi(k) s[d*k]^2)
#include<cstdio>
#include<iostream>
#include<cstring>
#define ll long long
#define R register ll
using namespace std;
namespace Luitaryi {
template<class I> inline I g(I& x) { x=0;
register I f=1; register char ch; while(!isdigit(ch=getchar())) f=ch=='-'?-1:f;
do x=x*10+(ch^48); while(isdigit(ch=getchar())); return x*=f;
} const int N=2e6;
int T,n,cnt,p[N>>1],phi[N+10],mu[N+10],c[N+10];
ll s[N+10],ans; bool v[N+10];
inline void PRE() { phi[1]=mu[1]=1;
for(R i=2;i<=N;++i) {
if(!v[i]) p[++cnt]=i,phi[i]=i-1,mu[i]=-1;
for(R j=1;j<=cnt&&i*p[j]<=N;++j) {
v[i*p[j]]=true;
if(i%p[j]==0) {
phi[i*p[j]]=phi[i]*p[j];
break;
} phi[i*p[j]]=phi[i]*(p[j]-1);
mu[i*p[j]]=-mu[i];
}
}
}
inline void calc(int n) { ans=0;
memset(c,0,sizeof(c)),memset(s,0,sizeof(s));
for(R i=1;i<=n;++i) ++c[phi[i]];
for(R i=1;i<=n;++i) for(R j=1,lim=n/i;j<=lim;++j) s[i]+=c[i*j];
for(R d=1;d<=n;++d) if(mu[d]) for(R k=1,lim=n/d;k<=lim;++k) //if(mu[d]) 优化枚举
ans+=mu[d]*phi[k]*s[d*k]*s[d*k];
}
inline void main() {g(T); PRE(); while(T--) g(n),calc(n),printf("%lld
",ans);}
} signed main() {Luitaryi::main(); return 0;}
2019.08.11
89