题目描述

给定一个$n$，对所有满足$1 \leq a, b, c$并且$a + b + c = n$的三元组$a, b, c$求$\sum lcm(c, gcd(a, b))$

数据范围

$1 \leq n \leq 10^5$

题解

首先$\sum lcm(c, gcd(a, b)) = \sum \frac{c \times gcd(a, b)}{gcd(gcd(a, b), c)}$

然后三个变量不好看，由于有$a + b + c = n$，所以可以把$b$用$n - a - c$表示，则由更相减损数得$gcd(a, b) = gcd(a, n - a - c) = gcd(a, n - c)$

原式变为$\sum \frac{c \times gcd(a, n - c)}{gcd(gcd(a, n - c), c)}$

考虑枚举$c$，原式变为$\sum c \sum \frac{gcd(a, n - c)}{gcd(gcd(a, n - c), c)}$，如果再枚举$a$的话时间复杂度就是$O(n^2)$的了，肯定过不了，所以考虑快速计算$\sum \frac{gcd(a, n - c)}{gcd((gcd(a, n - c), c)}$

~~然后就不会了~~

真正的题解

首先$\sum lcm(c, gcd(a, b))$，这个在化简的时候根本就不用展开

考虑枚举$c$，现在相当于$c$固定了，设$d = gcd(a, b)$，我们枚举$d$，求$gcd(a, b) = d$的有序对$(a, b)$的个数这个题就做出来了，当然这个过程的时间复杂度最高只能是$O(\sqrt n)$级别的

这就用到了我们上述推导中的$gcd(a, b) = gcd(a, n - c)$，这说明$d$必然是$n - c$的约数，而约数的个数恰好是根号级的

现在我们确定了$c$，确定了$d$，怎么求出有序对$(a, b)$的数量呢，可以看出我们只需要求出$gcd(a, n - c) = d$的$a$的数量就可以了

$a$显然应该是$d$的倍数，设$a = k_1 d, n - c = k_2 d$，那么既然$gcd(a, n - c) = d$，必然有$gcd(k_1, k_2) = 1$，

这里还应该有$k_1 < k_2$，而且在$c, d$固定的情况下$k_2$是已知的，则实际上$k_1$的数量就是$\phi(k_2) = \phi(\frac{n - c}{d})$

这也就是$a$的数量，也就是有序对$(a, b)$的数量

$\phi()$预处理就好了

这题不看题解我绝对想不到，而且看了题解还得琢磨一会才能明白

代码

#include <iostream>
#include <cstdio>
#include <cmath>

const int mod = 1e9 + 7;

int n;
int prm[112345], cnt, phi[112345];
bool np[112345];
int ans;

int Gcd(int a, int b)
{
    return b == 0 ? a : Gcd(b, a % b);
}

void Euler()
{
    phi[1] = 1;

    for(int i = 2; i <= n; i ++)
    {
        if(! np[i])
            prm[++ cnt] = i, phi[i] = i - 1;

        for(int j = 1; j <= cnt && i * prm[j] <= n; j ++)
        {
            np[i * prm[j]] = true;

            if(i % prm[j] == 0)
            {
                phi[i * prm[j]] = phi[i] * prm[j];

                break;
            }
            else
                phi[i * prm[j]] = phi[i] * (prm[j] - 1);
        }
    }
}

int main()
{
    scanf("%d", &n);

    Euler();

    for(int i = 1; i <= n - 2; i ++)
    {
        int sq = sqrt(n - i);

        for(int j = 1; j <= sq; j ++)
        {
            if((n - i) % j) continue;

            if(j != n - i) //d不能等于n - c， 否则有a = n - c, 这时b = 0, 不符合题意了
            {
                int tmp = 1LL * phi[(n - i) / j] * i * j / Gcd(i, j) % mod;

                ans = (1LL * ans + tmp) % mod;
            }

            int x = ((n - i) / j);

            if(x != j && x != n - i)
            {
                int tmp = 1LL * phi[(n - i) / x] * i * x / Gcd(i, x) % mod;

                ans = (1LL * ans + tmp) % mod;
            }
        }
    }

    printf("%d\n", ans);

    return 0;
}

Zth's Blog

cf818E. Madoka and The Best University 数学

题目描述

数据范围

题解

真正的题解

代码