首页 > 代码库 > HDU 1286 找新朋友(欧拉函数模板)

HDU 1286 找新朋友(欧拉函数模板)

HDU 1286 找新朋友

题意:中文题。

思路:欧拉函数的纯模板题,没什么好说的,主要是理解欧拉函数的意义。

在数论,对正整数n,欧拉函数是少于或等于n的数中与n互质的数的数目。此函数以其首名研究者欧拉命名,它又称为Euler‘s totient function、φ函数、欧拉商数等。 例如φ(8)=4,因为1,3,5,7均和8互质。   ----by度娘。

#include <stdio.h>

int eular(int n){
    int ret = 1;
    for(int i = 2; i*i <= n;i++)
        if(n%i == 0){
            n /= i, ret *= i-1;
            while(n%i == 0)
                n /= i, ret *= i;
        }
    if(n>1)
        ret *= n-1;
    return ret;
}

int T, n;

int main()
{
    scanf("%d", &T);
    while(T--)
    {
        scanf("%d", &n);
        printf("%d\n", eular(n));
    }

    return 0;
}