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("%lldn",euler(n));
56 return 0;
57 }
58
可以用来当做 求欧拉函数的模板
mdd的烦恼
时间限制:1000ms | 内存限制:65535KB难度: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
- 上传者
- 苗栋栋
原文链接: https://www.cnblogs.com/wujianwei/archive/2012/08/13/2637050.html
欢迎关注
微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍
原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/59123
非原创文章文中已经注明原地址,如有侵权,联系删除
关注公众号【高性能架构探索】,第一时间获取最新文章
转载文章受原作者版权保护。转载请注明原作者出处!