题解：SP5971 LCMSUM - LCM Sum

题目让你求：

$$\sum_{i = 1}^n \operatorname{lcm}(i, j)$$

推式子：

$$= \sum_{i = 1}^n \frac{i, n}{\gcd(i, n)}$$

$$= n \sum_{i = 1}^n \frac{i}{\gcd(i, n)}$$

$$= n \sum_{d | n} \sum_{i = 1}^{n} \frac{i}{d}[\gcd(i, n)=d]$$

$$= n \sum_{d | n} \sum_{i = 1}^{n/d} i[\gcd(id, n)=d]$$

$$= n \sum_{d | n} \sum_{i = 1}^{n/d} i[\gcd(i, \frac{n}{d})=1]$$

$$= n \sum_{d | n} \sum_{i = 1}^{d} i[\gcd(i, d)=1]$$

$$= n \sum_{d | n} \frac{d\phi(d)}{2}$$

到这里就直接可以预处理每个$n$的约数$\displaystyle \frac{d\phi(d)}{2}$值和了。

代码不开ios加速会TLE。

#include<bits/stdc++.h>
using namespace std;
#define int long long
vector<int> phisieve(int n)
{
    vector<int> primes, phi(n + 1);
    vector<bool> vis(n + 1, 0);
    phi[1] = 1, phi[0] = 0;
    vis[0] = vis[1] = 1;
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            phi[i] = i - 1;
            primes.push_back(i);
        }
        for (int j = 0; j < primes.size() && i * primes[j] <= n; j++) {  
            vis[i * primes[j]] = 1;
            if (i % primes[j]) {
                phi[i * primes[j]] = phi[i] * (primes[j] - 1);  
            } else {
                phi[i * primes[j]] = phi[i] * primes[j];  
                break;
            }
        }
    }
    return phi;
}
vector<int> phi;
vector<int> v(1e6 + 10, 0);
void solve()
{
    int n;
    cin >> n;
    cout << n * v[n] << '\n';
}
signed main()
{
    ios::sync_with_stdio();
    cin.tie(0);
    cout.tie(0);
    phi = phisieve(1e6 + 10);
    for (int i = 1; i <= 1e6; i++) {
        for (int j = 1; i * j <= 1e6; j++) {
            v[i * j] += (i == 1 ? 1 : i * phi[i] / 2);
        }
    }
    int T;
    cin >> T;
    while (T--) {
        solve();
    }
    return 0;
}