hdu1286 找新朋友 （歐拉函數法）

原題：點選打開連結

關于歐拉函數的算法詳細講解：點選打開連結

歐拉函數

1.歐拉函數是不完全積性函數。

2.歐拉函數p(x) = x * (p1 - 1) / p1 * (p2 - 1)/p2 * .....(pn - 1)/ pn;

#include <iostream>
#include <stdio.h>
#include <math.h>
using namespace std;

int euler(int x)//Euler 模闆
{
    int i, res = x;
    for(i = 2; i < (int) sqrt(x * 1.0)+1; i++)
        if(x % i == 0)
        {
            res = res / i * (i - 1);
            while(x % i == 0) x /= i; // 保證i一定是素數
        }
    if(x > 1)
        res = res / x * (x - 1);
    return res;
}
int main()
{
    int x;
    int Case;
    cin >> Case;
    while(Case--)
    {
        while(cin >> x)
        {
            cout <<euler(x) << endl;
        }
    }
    return 0;
}                

轉載于:https://my.oschina.net/u/1017188/blog/333600