|
Description Given n, a positive integer, how many positive integers less than n are relatively prime to n? Two integers a and b are relatively prime if there are no integers x > 1, y > 0, z > 0 such that a = xy and b = xz.
Input There are several test cases. For each test case, standard input contains a line with n <= 1,000,000,000. A line containing 0 follows the last case.
Output For each test case there should be single line of output answering the question posed above.
Sample Input
7
12
0
Sample Output
6
4
Source Waterloo local 2002.07.01
刚开始我傻X了，本着??的思维，照着欧拉函数的公式写了如下的代码，先筛素数然后分解质因数最后再算公式
//欧拉函数h(n)=n*(1-1/p1)*(1-1/p2)*'''''*(1-1/pk);
#include
#include
#include
#include
#define MAXN 1010 using namespace std; bool isPrime[MAXN]; int Prime[MAXN],PriNum[MAXN],cnt=0,tot=0; void GetPrime() { cnt=0; for(int i=1;i
>N; if(!N) break; DecQualityFactor(N); cout<
好吧这个代码根本没办法过，因为题目给的n的范围太大了，数组完爆内存，也就是说这题根本就不能用数组保存什么质因数和素数的。
下面才是真正的AC代码，又短又快神神哒
//欧拉函数h(n)=n*(1-1/p1)*(1-1/p2)*'''''*(1-1/pk);
#include
#include
#include
#include
#define MAXN 1000 using namespace std; int h(int n) { int ans=n; for(int i=2;i<=n;i++) { if(n%i==0) { ans=ans/i*(i-1); n/=i; while(n%i==0) n/=i; } } return ans; } int main() { while(1) { int N; cin>>N; if(!N) break; cout<
??
|