题解 UVA11426 【GCD - Extreme (II)】
岚雪
2018-10-16 16:20:26
对于原题中要求的式子$\displaystyle{\sum_{i=1}^n\sum_{j=i+1}^n\text{gcd}(i,j)}$,我们对其变形,得到$\displaystyle{\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)}$。
下面问题转换为求$\displaystyle{\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)}$,这个问题明显好求一些。
如果强行枚举$i,j$肯定是要超时的,所以我们改变思路枚举最大公约数的值,设为$k$。
注意到当且仅当$(a,b)=1$时会有$(ak,bk)=k$,所以对于每一个$k$,设$a,b$中较大的一个数为$a$,首先$a$必须满足$ak\leq n$,即$a\leq \lfloor \dfrac{n}{k}\rfloor$。
我们固定住$a$的值,由于$b<a$,所以此时$b$有$\varphi(a)$种选择,所以对于一个固定的$a$与$k$,对答案的贡献为$\varphi(a)\times k$。
注意到这里有一种特殊情况,由于在原式中$i$与$j$是不相等的,所以当$a=1$时无解。
所以对于每一个固定的$k$,有$\displaystyle{\sum_{i=2}^{\lfloor n/k\rfloor}(\varphi(i)\times k)=k\sum_{i=2}^{\lfloor n/k\rfloor}\varphi(i)=k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k}$
由于$k$有$1$到$n$共$n$种取法,所以最终答案为$\displaystyle{\sum_{k=1}^n\left(k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k\right)}$
但同时我们也可以直接证明$\displaystyle{\sum_{k=1}^n\left(k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k\right)=\sum_{i=1}^n\sum_{j=1}^{i-1}\text{gcd}(i,j)}$,下证其正确性。
证明:
$\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}}$
注意到在这里$\gcd(i,j)=d$可以写成$\gcd(\dfrac{i}{d},\dfrac{j}{d})=1$
所以原式$\displaystyle{=\sum_{d=1}^n\left(d\sum_{i=1}^{\lfloor n/d\rfloor}\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)}$
证毕。
注意到$\displaystyle{k\sum_{i=1}^{\lfloor n/k\rfloor}\varphi(i)-k}$是可以先线性处理欧拉函数前缀和然后$\text O(1)$查询的,所以整个求和式可以在$\text{O}(n)$内做出来。
---
```cpp
#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;
}
```