Description
给出一个数字N
Input
第一行为一个正整数T，表示数据组数。
接下来T行为询问，每行包含一个正整数N。
T<=5000,N<=10^7
Output
按读入顺序输出答案。
Sample Input
1
10Sample Output
136
Solution
莫比乌斯反演。
还有一种用欧拉函数的\[ \begin{aligned} &\sum_{i=1}^{n}\sum_{j=1}^n\phi((i,j))\\ &=\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{n}\sum_{j=1}^n[(i,j)=d]\\ &=\sum_{d=1}^{n}\phi(d)\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{k|(i,j)}\mu(k)\\ &=\sum_{d=1}^{n}\phi(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{kd}\rfloor^2\mu(k) \end{aligned} \]
这样可以做到单次询问\(O(n)\)，可以继续推下去
\[ \begin{aligned} &设T=kd\\ &\sum_{d=1}^{n}\phi(d)\sum_{k=1}^{\lfloor\frac{n}{d}\rfloor}\lfloor\frac{n}{kd}\rfloor^2\mu(k)\\ &=\sum_{T=1}^{n}\lfloor\frac{n}{T}\rfloor^2\sum_{k|T}\mu(k)\phi(\frac{T}{k})\\ \end{aligned} \] 发现后面那个玩意是个狄利克雷卷积形式，所以这玩意是个积性函数，上线性筛当\(T\)为质数时
\[ \begin{aligned} &\sum_{k|T}\mu(k)\phi(\frac{T}{k})\\ &=\mu(1)*\phi(T)+\mu(T)*\phi(1)\\ &=T-1-1\\ &=T-2 \end{aligned} \] 当\(T\)为质数的平方时\[ \begin{aligned} &\sum_{k|T}\mu(k)\phi(\frac{T}{k})\\ &=\phi(p)*\mu(p)+\phi(p^2)*\mu(1)\\ &=-(p-1)+p(p-1)\\ &=-p+1+p^2-p\\ &=p^2-2p+1\\ &=(p-1)^2 \end{aligned} \] 当\(T\)为质数的\(c\)次方时（\(c>2\)）\[ \begin{aligned} &设c=3\\ &\sum_{k|T}\mu(k)\phi(\frac{T}{k})\\ &=\phi(p^3)*\mu(1)-\phi(p^2)*\mu(p)+0\\ &=p^3-p^2-p^2+p\\ &=p^3-2p^2+p\\ &=p(p^2-2p+1)\\ &=p(p-1)^2 \end{aligned} \] 同理可得当\(T=p^c（c>2）\)时，该函数的值为\(p^{c-2}(p-1)^2\)但是有这个\(p=2\)有点麻烦，所以我们不妨直接分类讨论这两种情况
考虑在线性筛中遇到这种情况怎么搞
设以上讨论的那个函数为\(f\)
1.当i不为prime[j]倍数
根据积性函数的定义即可
\[ f(i*prime[j])=f(i)*f(prime[j]) \]2.当\(i\)为\(prime[j]\)倍数
当\(i\)中\(prime[j]\)的指数为\(1\)时，对应上方的\(T=p^2\)的情况
（注：因为指数为\(1\)，所以\(i/prime[j]\)与\(prime[j]\)互质）
\[ \begin{aligned} &f(i*prime[j])\\ &=f(i/prime[j])*f(prime[j]^2)\\ &=f(i/prime[j])*(prime[j]-1)^2 \end{aligned} \] 当\(i\)中\(prime[j]\)的质数大于\(1\)时，对应上方\(T=p^c(c>2)\)，将结论代入即可\[ \begin{aligned} &f(i*prime[j])\\ &=f(i)*prime[j]\\ \end{aligned} \] （注：因为\(f(i)\)其实就是\(T=p^{c-1}\)的情况，所以直接按照上方的结论乘上p即可）然后就做完了
复杂度\(O(n+T\sqrt{n})\)
#includeusing namespace std;typedef long long ll;const int N = 1e7 + 10;ll p[N];ll n, cnt;ll F[N], sum[N];bool vis[N];inline void init() { F[1] = 1; for(int i = 2; i < N; ++i) { if(!vis[i]) p[++cnt] = i, F[i] = i - 2; for(int j = 1; j <= cnt && i * p[j] < N; ++j) { vis[i * p[j]] = 1; if(i % p[j] == 0) { if((i / p[j]) % p[j]) F[i * p[j]] = F[i / p[j]] * (p[j] - 1) * (p[j] - 1); //有平方质因子 else F[i * p[j]] = F[i] * p[j]; //有平方以上的质因子 break; } F[i * p[j]] = F[i] * F[p[j]]; } } for(int i = 1; i < N; ++i) F[i] += F[i - 1];}inline ll calc(ll n) { ll ans = 0; for(ll l = 1, r; l <= n; l = r + 1) { r = n / (n / l); ans += (n / l) * (n / l) * (F[r] - F[l - 1]); } return ans;}int main() { int T; scanf("%d", &T); init(); while(T--) { scanf("%lld", &n); printf("%lld\n", calc(n)); }}