poj 2407(欧拉函数)

poj 2407
简单的求$\varphi(n)$,复习了一下模板

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<cmath>
#define ms(i,j) memset(i,j, sizeof i);
using namespace std;
int phi(int n)
{
int m = sqrt(n+0.5);
int ans = n;
for (int i=2;i<=m;i++)
if (n%i==0)
{
ans = ans/i*(i-1);
while (n%i==0) n /= i;
}
if (n>1) ans = ans/n*(n-1);
return ans;
}
int main()
{
int n;
while (scanf("%d", &n)==1 && n)
{
printf("%d\n", phi(n));
}
return 0;
}

------ 本文结束 ------