题目链接: http://poj.org/problem?id=2407
题目大意：求小于n且与n互质的正整数个数。
解题思路：
欧拉函数=小于n且与n互质的正整数个数。
公式=n*(1-1/P1)*(1-1/P2)....*(1-1/Pn)，其中Pn为不同的质因数。
欧拉函数的求法有好多。
最简单的是手艹质因数分解，然后套公式计算。
注意特判1的时候ans=0.
#include "cstdio"
#include "map"
using namespace std;
#define LL long long
map<LL,LL> prime_factor(LL n)
{
map<LL,LL> res;
for(int i=;i*i<=n;i++)
while(n%i==) {++res[i];n/=i;}
if(n!=) res[n]=;
return res;
}
int main()
{
LL n;
while(scanf("%I64d",&n)!=EOF&&n)
{
if(n==) {printf("0\n");continue;}
map<LL,LL> fac=prime_factor(n);
LL ret=n;
for(map<LL,LL>::iterator i=fac.begin();i!=fac.end();i++)
ret=ret/i->first*(i->first-);
printf("%I64d\n",ret);
}
}
| 13625955 | neopenx | 2407 | Accepted | 148K | 0MS | C++ | 573B | 2014-11-13 16:20:05 |