nyoj 333 mdd的烦恼

View Code

 1  
 2 /*********************************
 3 /   Problem:
 4 /   Algorithm:
 5 /   Language:   C++
 6 /   Compiler:   MinGW
 7 /   Date:       12/08/07
 8 /
 9 /   Copyright (C) wujianwei
10 /   All rights reserved.
11 ********************************/
12 
13 #include <iostream>
14 #include <cstdio>
15 #include <cstring>
16 #include <cmath>
17 #include <vector>
18 #include <cstring>
19 #include <queue>
20 #include <stack>
21 #include <algorithm>
22 #include <set>
23 
24 using namespace std;
25 
26 #define INF 0x7fffffff
27 #define EPS 1e-12
28 #define MOD 1000000007
29 #define PI 3.141592653579798
30 #define N 100000
31 const int MAX=1<<28;
32 typedef long long LL;
33 //typedef __int64 INT
34 
35 LL euler(LL n)
36 {
37     LL sum=n,i;
38     for(i=2; i*i<=n; i++)
39     {
40         if(n%i==0)
41         {
42             sum=sum*(i-1)/i;
43             while(n%i==0) n/=i;
44             if(n==1) break;
45         }
46     }
47     if(n!=1) sum=sum*(n-1)/n;
48     return sum;
49 }
50 
51 int main()
52 {
53     LL n;
54     while(~scanf("%lld",&n))
55         printf("%lld\n",euler(n));
56     return 0;
57 }
58

可以用来当做求欧拉函数的模板

mdd的烦恼

时间限制：1000 ms | 内存限制：65535 KB

难度：3

描述: 今天mdd看到这么一段话：在数论，对正整数n，欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名，它又称为Euler's totient function、φ函数、欧拉商数等。例如φ(8)=4，因为1,3,5,7均和8互质。于是他想用计算机实现欧拉函数的功能，但是他又不想去写，你能帮帮他吗？

ps:互质（relatively primeì）又叫互素。若N个整数的最大公因数是1，则称这N个整数互质。

输入

有多组测试数据组数小于1003，
每组测试数据有一个整数n(0<n<=65535^2+1).

输出

输出欧拉函数φ(n)的值。

样例输入

2
6
46

样例输出

1
2
22

上传者

苗栋栋

nyoj 333 mdd的烦恼

可以用来当做 求欧拉函数的模板

mdd的烦恼

可以用来当做求欧拉函数的模板