以下内容摘自

 

求欧拉函数值

 

long long Euler(long long n){    long long ans = n;    for (long long i = 2; i * i <= n; i++)    {        if (n % i == 0)        {            ans = ans - ans / i;            while (n % i == 0) n /= i;        }    }    if (n > 1)        ans = ans - ans / n;    return ans;}

void init(){    for (int i = 1; i < maxn; i++) Euler[i] = i;    for (int i = 2; i < maxn; i += 2) Euler[i] >>= 1;    for (int i = 3; i < maxn; i += 2)    {        if (Euler[i] == i)        {            for (int j = i; j < maxn; j += i)                Euler[i] = Euler[i] - Euler[i] / i;        }    }}