SGU 102 Coprimes

SGU_102

    一开始直接用gcd暴力也能过，后来看了别人的解题报告发现可以用欧拉函数，以前用过一次但现在忘记了，于是又学了一遍。

#include<stdio.h>
#include<string.h>
#include<math.h>
int N;
void solve()
{
    int i, j, k = (int)sqrt(N + 1), res = N;
    for(i = 2; i <= k; i ++)
        if(N % i == 0)
        {
            res = res / i * (i - 1);
            while(N % i == 0)
                N /= i;
        }
    if(N > 1)
        res = res / N * (N - 1);
    printf("%d\n", res);
}
int main()
{
    while(scanf("%d", &N) == 1)
        solve();
    return 0;
}