_yxl_gl_的博客

_yxl_gl_的博客

题解 UVA11426 【GCD - Extreme (II)】

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

对于原题中要求的式子 $\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)$ 内做出来。


#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;
}