## 【数论】线筛积性函数/莫比乌斯反演

### 传送门

f(n) = \sum\limits_i^n\sum\limits_j^n\phi(gcd(i,j))，给定T<=5000组询问，每次n<=1e9

ans = \sum\limits_p\sum\limits_{p|d}\mu(\frac{d}{p})\lfloor\frac{n}{d}\rfloor\lfloor\frac{n}{d}\rfloor\phi(p)
ans = \sum\limits_p\sum\limits_{d=1}\mu(d)\lfloor\frac{n}{dp}\rfloor\lfloor\frac{n}{dp}\rfloor\phi(p)

ans = \sum\limits_T\lfloor\frac{n}{T}\rfloor\lfloor\frac{n}{T}\rfloor\sum\limits_{p|T}\mu(\frac{T}{p})\phi(p)

h(T) = \sum\limits_{p|T}\mu(\frac{T}{p})\phi(p)，想办法处理这个函数的前缀和，与前面整除分块一起计算

h(pri^x) = \phi(pri^x) – \phi(pri^{x-1})

### 线筛的方法如下：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
const int maxn = 1e7 + 233;
int st[maxn];
ll primes[maxn], f[maxn], h[maxn], phi[maxn], low[maxn], cnt;
void get_primes(ll n)
{
f[1] = 1; phi[1] = 1; low[1] = st[1] = 1;
for(ll i = 2; i <= n; i++)
{
if(!st[i]) low[i] = primes[cnt++] = i, phi[i] = i - 1, f[i] = phi[i] - 1;
for(int j = 0; j < cnt && i * primes[j] <= n; j++)
{
st[i * primes[j]] = 1;
if(i % primes[j] == 0)
{
low[i * primes[j]] = low[i] * primes[j];
phi[i * primes[j]] = phi[i] * primes[j];
if(low[i] == i) f[i * primes[j]] = phi[i * primes[j]] - phi[i];
else f[i * primes[j]] = f[i / low[i]] * f[low[i] * primes[j]];
break;
}
low[i * primes[j]] = primes[j];
phi[i * primes[j]] = phi[i] * (primes[j] - 1);
f[i * primes[j]] = f[i] * (phi[primes[j]] - 1);
}
}
for(int i = 1; i <= n; i++) h[i] = f[i] + h[i - 1];
}
int main()
{
int T; cin >> T;
get_primes(10000010);
//for(int i = 1; i <= 10; i++) cout << f[i] << ' '; puts(" ");
//for(int i = 1; i <= 10; i++) cout << h[i] << ' '; puts(" ");
while(T--)
{
ll n;
scanf("%lld", &n);
//n = T;
ll c = 0, ans = 0;
for(ll i = 1; i <= n; i = c + 1)
{
c = n / (n / i);
ans = ans + (h[c] - h[i - 1]) * ((n / i) * (n / i));
}
printf("%lld\n", ans);
}
}