76-Relatives-欧拉函数
http://poj.org/problem?id=2407
Relatives
| Time Limit: 1000MS | Memory Limit: 65536K | |
| Total Submissions: 16652 | Accepted: 8470 |
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
思路：欧拉函数板子题，就是就给定数字的欧拉函数
#include <iostream>
using namespace std;
#define LL long long
LL Phi(LL x){ //按定义直接算
if(x == 1){
return 1;
}
LL ans = x;
for(int i = 2; i * i <= x; i++){
if(x % i == 0){
ans = ans / i * (i - 1);
while(x % i == 0){
x = x / i;
}
}
}
// cout << ans << " " << x << endl;
if(x >= 2)
ans = ans / x * (x - 1);
return ans;
}
//bool visit[10001];
//int tot=0, pri[1000005], phi[1000005];
//LL Phi(LL n){ //线性筛选
// phi[1] = 1;
// for(int i = 2; i <= n; i++){
// if(!visit[i]){
// pri[++tot] = i;
// phi[i] = i - 1;
// }
// for(int j = 1, x; j <= tot && (x = i * pri[j]) <= n; j++){
// visit[x] = true;
// if(i % pri[j] == 0){ //不互质时
// phi[x] = phi[i] * pri[j];
// break;
// }
// else{
// phi[x] = phi[i] * phi[pri[j]];
// }
// }
// }
// return phi[n];
//}
int main(){
LL x;
while(cin >> x && x){
cout << Phi(x) << endl;
}
return 0;
}