题目链接: 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 |