POJ2480:Longge’s Problem 题解

主要思路和结论

给定一个\(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

发布者

Kal0rona

江西师大附中全机房最弱

发表评论

电子邮件地址不会被公开。 必填项已用*标注