# GCD - Extreme (II)

## 解法一：蓝书解法，计算贡献

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EulerSieve
{
vector<int> p, m, phi;
EulerSieve(int N) : m(N, 0), phi(N, 0)
{
phi[1] = 1;
for (long long i = 2, k; i < N; ++i)
{
if (!m[i])
p.push_back(m[i] = i), phi[i] = i - 1;
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
phi[k] = phi[i] * p[j];
if ((m[k] = p[j]) == m[i])
break;
phi[k] -= phi[i];
}
}
}
};
struct GCDExtremeII : EulerSieve
{
vector<ll> f;
GCDExtremeII(int N) : EulerSieve(N), f(N)
{
for (int i = 1; i < N; ++i)
{
for (int k = 2; k * i < N; ++k)
f[k * i] += i * phi[k];
f[i] += f[i - 1];
}
}
} g(4e6 + 9);
int main()
{
for (int n; ~scanf("%d", &n) && n;)
printf("%lld\n", g.f[n]);
}

## 解法二：分块

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EulerSieve
{
vector<int> p, m, phi;
vector<ll> sum;
EulerSieve(int N) : m(N, 0), phi(N, 0), sum(N, 0)
{
phi[1] = 1;
for (long long i = 2, k; i < N; ++i)
{
if (!m[i])
p.push_back(m[i] = i), phi[i] = i - 1;
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
phi[k] = phi[i] * p[j];
if ((m[k] = p[j]) == m[i])
break;
phi[k] -= phi[i];
}
}
for (int i = 0; i < N; ++i)
sum[i] = sum[i - 1] + phi[i];
}
} e(4e6 + 9);
int main()
{
for (ll n, sum, tmp; ~scanf("%lld", &n) && n;)
{
for (int i = 1, j = sum = 0; i <= n; i = j + 1)
tmp = n / i, sum += tmp * tmp * (e.sum[j = n / tmp] - e.sum[i - 1]);
printf("%lld\n", (sum - (n + 1) * n / 2) / 2);
}
}

## 解法三：莫比乌斯反演

$ans=\sum_{d=1}^nd\sum_{i=1}^{n/d}\mu(i)[\frac{n}{id}]^2=\sum_{T=1}^n[\frac{n}{T}]^2\sum_{d|T}d\mu(\frac{T}{d})$ 数论分块可$O(\sqrt n)$查询，总时间复杂度$O(n\sqrt n)$。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
struct EulerSieve
{
vector<int> p, m, mu, sum; //素数序列，最小素因子，欧拉函数，莫比乌斯函数
EulerSieve(int N) : m(N, 0), mu(N, 0), sum(N, 0)
{
mu[1] = 1;							 //m[1]=0
for (long long i = 2, k; i < N; ++i) //防i*p[j]爆int
{
if (!m[i])
p.push_back(m[i] = i), mu[i] = -1; //i是素数
for (int j = 0; j < p.size() && (k = i * p[j]) < N; ++j)
{
if ((m[k] = p[j]) == m[i])
{
mu[k] = 0;
break;
}
mu[k] = -mu[i];
}
}
for (int i = 1; i < N; ++i)
sum[i] = sum[i - 1] + mu[i];
}
} e(4e6 + 9);
int main()
{
for (ll n, sum, tmp; ~scanf("%lld", &n) && n;)
{
sum = 0;
for (int i = 1; i <= n; ++i)
for (ll l = 1, r, tmp, m = n / i; l <= m; l = r + 1)
tmp = m / l, sum += i * tmp * tmp * (e.sum[r = m / tmp] - e.sum[l - 1]);
printf("%lld\n", (sum - (n + 1) * n / 2) / 2);
}
}