CF #818 E - Madoka and The Best University

欧拉函数，枚举

Problem - E - Codeforces

题意

给定整数 \(n(1<=n<=10^5)\), 对于所有的正整数三元组 \((a,b,c)\) ，求 \(lcm(c,gcd(a,b))\) 的和

思路

对于数论题可以多尝试几种枚举顺序，可能会利用到某些性质优化

首先若枚举 c, 再枚举 a, 复杂度为 \(O(n^2)\)

枚举 a, b 也是 \(O(n^2)\)

若枚举 \(d=gcd(a,b)\), 再枚举 \(a+b=t*d\;(t>=2)\)

即从 \([1,n]\)枚举 d，t 从 2 枚举到 t * d > n, 根据调和级数，枚举的复杂度为 \(O(nlogn)\)

此时 \(gcd(a,b)=d, a+b=t*d, c=n-t*d\)

找到有多少对 \((a,b)\), 满足 \(gcd(a,b)=d\;且\;a+b=t*d\)，即可

同时除以 d, 即找到有多少对 \((a,b)\), 满足 \(a+b=t\) 且 a,b 互质，答案即为 \(\phi(t)\)

因此本次枚举对答案的贡献为 \(\phi(t)*lcm(n-t*d,d)\)

#include <iostream>
#include <algorithm>
#include <cstring>
#include <vector>
#include <cmath>

using namespace std;
#define endl "\n"

typedef long long ll;
typedef pair<int, int> PII;

const int N = 1e5 + 10, mod = 1e9 + 7;
int n;
int phi[N];
int pr[N], p[N], pe[N], cnt;

void get_primes(int n)
{
    p[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (!p[i])
        {
            p[i] = i;
            pr[++cnt] = i;
            pe[i] = i;
        }
        for (int j = 1; j <= cnt && pr[j] <= n / i; j++)
        {
            p[i*pr[j]] = pr[j];
            if (p[i] == pr[j])
            {
                pe[i*pr[j]] = pe[i] * pr[j];
                break;
            }
            pe[i*pr[j]] = pr[j];
        }
    }
}

void presolve(int n)
{
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (pe[i] != i)
            phi[i] = phi[i/pe[i]] * phi[pe[i]];
        else
            phi[i] = i / p[i] * (p[i] - 1);
    }
}
ll gcd(ll a, ll b)
{
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

ll lcm(ll a, ll b)
{
    return a / gcd(a, b) * b % mod;
}
int main()
{
    ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
    cin >> n;
    get_primes(n);
    presolve(n);
    ll ans = 0;
    for (int d = 1; d <= n; d++)
    {
        for (int t = 2; t * d <= n; t++)
        {
            int c = n - t * d;
            ans += lcm(c, d) * phi[t] % mod;
            ans %= mod;
        }
    }
    cout << ans << endl;
    return 0;
}