(Relax 数论1.7)POJ 2407 Relatives(使用欧拉函数来求[1,n]中与n互质的整数的个数)

 
/* 
 * POJ_2407.cpp 
 * 
 *  Created on: 2013年11月19日 
 *      Author: Administrator 
 */  
  
#include   
#include   
#include   
  
using namespace std;  
  
typedef long long ll;  
  
const int maxn = 1000015;  
  
bool u[maxn];  
ll su[maxn];  
ll num;  
  
ll gcd(ll a, ll b) {  
    if (b == 0) {  
        return a;  
    }  
  
    return gcd(b, a % b);  
}  
  
void prepare() {//欧拉筛法产生素数表  
    ll i, j;  
    memset(u, true, sizeof(u));  
  
    for (i = 2; i <= 1000010; ++i) {  
        if (u[i]) {  
            su[++num] = i;  
        }  
  
        for (j = 1; j <= num; ++j) {  
            if (i * su[j] > 1000010) {  
                break;  
            }  
  
            u[i * su[j]] = false;  
  
            if (i % su[j] == 0) {  
                break;  
            }  
        }  
    }  
}  
  
ll phi(ll x) {//欧拉函数,用于求[1,x)中与x互质的整数的个数  
    ll ans = 1;  
    int i, j, k;  
    for (i = 1; i <= num; ++i) {  
        if (x % su[i] == 0) {  
            j = 0;  
            while (x % su[i] == 0) {  
                ++j;  
                x /= su[i];  
            }  
  
            for (k = 1; k < j; ++k) {  
                ans = ans * su[i] % 1000000007ll;  
            }  
            ans = ans * (su[i] - 1) % 1000000007ll;  
            if (x == 1) {  
                break;  
            }  
        }  
    }  
  
    if (x >





 1) {  
        ans = ans * (x - 1) % 1000000007ll;  
    }  
  
    return ans;  
}  
  
int main() {  
    prepare();  
  
    int n;  
    while (scanf("%d", &n) != EOF, n) {  
        printf("%lld\n", phi(n));  
    }  
  
    return 0;  
}