主要思路和结论

给定一个\(n\)，求\(\sum_{i=1}^{n} \gcd(i,n)\)。

题意非常的小清新，然而推式子的时候很伤心。我一开始使用打表的方法，一直没成功发现其中的规律。所以推式子的能力还是相当重要的。

我们来分析一下。对于\(i\in [1,n], gcd(i,n)=1\)，它们对答案的贡献是\(\phi(n)\)。之后来看另一部分，也就是\(j\in [1,n], gcd(j,n)=k, k \neq 1\)，我们可以除下，变成\(k*gcd(\frac{j}{k},\frac{n}{k})=k, gcd(\frac{j}{k},\frac{n}{k})=1\)，其中根据欧拉定理，有\(\phi(k)\)个这样的\(gcd\)，所以推出得\(k*\phi(k)\)。答案最后只需统计\(k\)的因数乘上\(\phi(因数)\)即可。

最后可以考虑使用 map 记录已计算过的欧拉值，可获得常数优化。

代码

// POJ2480.cpp
#include <cstdio>
#include <iostream>
#include <vector>
#include <map>
#define ll long long
using namespace std;
map<ll, ll> prefix;
vector<ll> getFracted(ll x)
{
    vector<ll> res;
    for (ll i = 1; i * i <= x; i++)
        if (x % i == 0)
        {
            res.push_back(i);
            if (i != x / i)
                res.push_back(x / i);
        }
    return res;
}
ll phi(ll x)
{
    ll ans = x;
    for (ll i = 2; i * i <= x; i++)
        if (x % i == 0)
        {
            ans -= ans / i;
            while (x % i == 0)
                x /= i;
        }
    if (x > 1)
        ans -= ans / x;
    return ans;
}
int main()
{
    ll n;
    while (scanf("%lld", &n) != EOF)
    {
        ll ans = 0;
        vector<ll> container = getFracted(n);
        ll siz = container.size();
        for (int i = 0; i < siz; i++)
        {
            if (!prefix.count(n / container[i]))
                prefix[n / container[i]] = phi(n / container[i]);
            ll e = prefix[n / container[i]];
            ans += e * container[i];
        }
        printf("%lld\n", ans);
    }
    return 0;
}

src:https://www.cnblogs.com/neopenx/p/4095691.html