hdu 1787(欧拉函数)
2024-09-08 14:16:34
GCD Again
Time Limit: 1000/1000 MS (Java/Others) Memory Limit: 32768/32768 K (Java/Others)
Total Submission(s): 2874 Accepted Submission(s): 1240
Problem Description
Do you have spent some time to think and try to solve those unsolved problem after one ACM contest?
No? Oh, you must do this when you want to become a "Big Cattle".
Now you will find that this problem is so familiar:
The
greatest common divisor GCD (a, b) of two positive integers a and b,
sometimes written (a, b), is the largest divisor common to a and b. For
example, (1, 2) =1, (12, 18) =6. (a, b) can be easily found by the
Euclidean algorithm. Now I am considering a little more difficult
problem:
Given an integer N, please count the number of the integers M (0<M<N) which satisfies (N,M)>1.
This
is a simple version of problem “GCD” which you have done in a contest
recently,so I name this problem “GCD Again”.If you cannot solve it
still,please take a good think about your method of study.
Good Luck!
No? Oh, you must do this when you want to become a "Big Cattle".
Now you will find that this problem is so familiar:
The
greatest common divisor GCD (a, b) of two positive integers a and b,
sometimes written (a, b), is the largest divisor common to a and b. For
example, (1, 2) =1, (12, 18) =6. (a, b) can be easily found by the
Euclidean algorithm. Now I am considering a little more difficult
problem:
Given an integer N, please count the number of the integers M (0<M<N) which satisfies (N,M)>1.
This
is a simple version of problem “GCD” which you have done in a contest
recently,so I name this problem “GCD Again”.If you cannot solve it
still,please take a good think about your method of study.
Good Luck!
Input
Input
contains multiple test cases. Each test case contains an integers N
(1<N<100000000). A test case containing 0 terminates the input and
this test case is not to be processed.
contains multiple test cases. Each test case contains an integers N
(1<N<100000000). A test case containing 0 terminates the input and
this test case is not to be processed.
Output
For each integers N you should output the number of integers M in one line, and with one line of output for each line in input.
Sample Input
2
4
0
4
0
Sample Output
0
1
1
水题一枚
#include <stdio.h>
#include <string.h>
using namespace std;
typedef long long LL;
LL phi(LL x)
{
LL ans=x;
for(LL i=; i*i<=x; i++)
if(x%i==)
{
ans=ans/i*(i-);
while(x%i==) x/=i;
}
if(x>)
ans=ans/x*(x-);
return ans;
} int main(){
LL n;
while(scanf("%lld",&n)!=EOF,n){
printf("%lld\n",n-phi(n)-);
}
}
最新文章
- Objective-C 源码初探 __attribute__
- yii框架中的一些小细节配置问题
- 绘图: Shape, Path
- BZOJ 3365: [Usaco2004 Feb]Distance Statistics 路程统计
- Java堆栈的应用2----------中缀表达式转为后缀表达式的计算Java实现
- jquery table 拼接集合
- 初学Flask(1)
- [转]shell脚本打印日志方法
- getView 数据最后加一项
- Windows 技巧
- javaWeb学习总结(4)- HttpServletResponse
- 给Linux RedHat7 设置启动终端的快捷键
- POJ-3045 Cow Acrobats (C++ 贪心)
- BZOJ 1856: [Scoi2010]字符串 [Catalan数]
- visual studio 2010 Error: IntelliSense: identifier ";DWORD"; is undefined
- eclipse 工作区空格和回车键显示为乱码
- Interllij IDEA中启动web项目
- Android Handler的内存泄露问题+解决方案
- FIR特性及仿真实现_01
- 【TCP/IP详解 卷一:协议】第十二章 广播和多播