POJ 2480 (约数+欧拉函数)

题目链接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
上一篇:Oracle 11g oracle客户端(32位)PL/SQL develepment的安装配置


下一篇:Java项目案例之---常用工具类练习