# _yxl_gl_的博客

### 题解 UVA11426 【GCD - Extreme (II)】

posted on 2018-10-16 16:20:26 | under 题解 |

$\displaystyle{\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)=\sum_{i=1}^n\sum_{j=1}^{i}\text{gcd}(i,j)-\dfrac{n(1+n)}{2}}$

$\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^n\sum_{j=1}^{i}\left[\gcd(i,j)=d\right]\right)-\dfrac{n(1+n)}{2}}$

$\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^{\lfloor n/d\rfloor}\varphi(i)\right)-\dfrac{n(1+n)}{2}}$

$\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^{\lfloor n/d\rfloor}\varphi(i)-d\right)}$

#include <cstdio>
#include <iostream>
using namespace std;
typedef long long ll;

const int N = 4000005;

ll n, cnt, vis[N], prime[N], phi[N];
int main() {
//  freopen("Uva11426.in", "r", stdin);
//  freopen("Uva11426.out", "w", stdout);
ios::sync_with_stdio(false);
// 预处理欧拉函数
phi[1] = 1;
for (int i = 2; i <= N - 5; i ++) {
if (!vis[i]) {
prime[++ cnt] = i;
phi[i] = i - 1;
vis[i] = i;
}
for (int j = 1; j <= cnt; j ++) {
if (prime[j] > vis[i] || prime[j] * i > N - 5)
break;
vis[i * prime[j]] = prime[j];
if (i % prime[j] != 0)
phi[i * prime[j]] = phi[i] * (prime[j] - 1);
else
phi[i * prime[j]] = phi[i] * prime[j];
}
}
for (int i = 2; i <= N - 5; i ++)
phi[i] += phi[i - 1];
while (true) {
cin >> n;
if (n == 0)
return 0;
long long ans = 0;
for (int i = 1; i <= n; ++ i)
ans += (phi[n / i] - 1) * i;
cout << ans << endl;
}
return 0;
}