P2398 GCD SUM

题意:

求

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

思路:

• $30pts$ - 暴力枚举 - $O(n^2logn)$
• $100pts$ - 考虑枚举$gcd(i,j) = k$ - $O(n)$
  对于$\forall$$gcd(i,j)=1$，有$gcd(i*k,j*k)=k$
  而$gcd(1,1)=1$我们不能重复计算，所以$gcd(i,j)=k$的个数为:

$$2*\sum_{i=1}^{\left \lfloor \frac{n}{k} \right \rfloor } \varphi (i)-1 $$

本题枚举$i:1\to$ $n$累计$k$的贡献即可，可以使用前缀和优化区间查询

参考代码:

#include <bits/stdc++.h>
using namespace std;
#define int long long
#define endl '\n'
const int N = 1e5 + 5;
int n, ans;
int pri[N], tot;
int phi[N], sum[N];
bitset<N> p;
inline void getPrimes(int lim)
{
    p.set();
    p[0] = p[1] = false;
    phi[1] = 1;
    for (int i = 2; i <= n; i++)
    {
        if (p[i])
            pri[++tot] = i, phi[i] = i - 1;
        for (int j = 1; j <= tot && i * pri[j] <= lim; j++)
        {
            p[i * pri[j]] = false;
            if (i % pri[j] == 0)
            {
                phi[i * pri[j]] = phi[i] * pri[j];
                break;
            }
            else
                phi[i * pri[j]] = phi[i] * phi[pri[j]];
        }
    }
    for (int i = 1; i <= n; i++)
        sum[i] = sum[i - 1] + phi[i];
}
signed main()
{
    ios::sync_with_stdio(false);
    cin.tie(0);
    cin >> n;
    getPrimes(n);
    for (int i = 1; i <= n; i++)
        ans += (sum[n / i] * 2 - 1) * i;
    cout << ans << endl;
}