POJ 2480 (约数+欧拉函数)

时间：2023-03-23 22:10:14

题目链接: http://poj.org/problem?id=2480

题目大意：求Σgcd(i,n)。

解题思路：

如果i与n互质，gcd(i,n)=1，且总和=欧拉函数phi(n)。

如果i与n不互质，那么只要枚举n的全部约数，对于一个约数d，若使gcd(i/d,n/d)互质，这部分的gcd和=d*欧拉函数phi(n/d).

不断暴力从小到大枚举约数，这样就把gcd和切成好多个部分，累加起来就行了。

其实还可以公式化简，不过实在太繁琐了。可以参考金海峰神的解释。

由于要求好多欧拉函数，每次都分解质因数法必然TLE，这里所以采用O(√n)求单个欧拉函数+Hash记录打表的方法。

#include "cstdio"

#include "vector"

#include "map"

using namespace std;

#define LL long long

vector<LL> divisor(LL n)

{

    vector<LL> res;

    for(LL i=;i*i<=n;i++)

        if(n%i==)

        {

            res.push_back(i);

            if(i!=n/i) res.push_back(n/i);

        }

    return res;

}

LL eular(LL  n)

{

    LL ans=n;

    for(LL i=;i*i<=n;i++)

    {

        if(n%i==)

        {

            ans-=ans/i;

            while(n%i==) n/=i;

        }

    }

    if(n>) ans-=ans/n;

    return  ans;

}

int main()

{

    LL n;

    map<LL,LL> table;

    while(scanf("%I64d",&n)!=EOF)

    {

       LL ans=;

       vector<LL> div=divisor(n);

       for(int i=;i<div.size();i++)

       {

           LL e;

           if(!table.count(n/div[i])) {table[n/div[i]]=eular(n/div[i]);e=table[n/div[i]];}

           else e=table[n/div[i]];

           ans+=(div[i]*e);

       }

       printf("%I64d\n",ans);

    }

}
13626576 neopenx 2480 Accepted 556K 360MS C++ 1121B 2014-11-13 19:24:55

相关文章