现在的位置: 首页 > 综合 > 正文

欧拉函数

2017年12月16日 ⁄ 综合 ⁄ 共 588字 ⁄ 字号 评论关闭

欧拉函数:phi(n) = the number of i where gcd(i,n) = 1 and 1 <= i <= n.

解法:容斥原理。

先将 n 分解质因数,然后 phi(n) = Σphi(p_i) - Σphi(p_i * p_j) + Σphi(p_i * p_j * p_k)  - ... 。

可简化成式子 phi(n) = n * (1 - 1/pi) * (1 - 1/pj) * ... 。

在线版。

#include <stdio.h>

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

预处理版。

#include <stdio.h>

const int N = 1e5 + 5;

int phi[N];

void pre_euler()
{
    phi[1] = 1;
    for(int i=2;i<N;i++)
    {
        if(!phi[i])
        {
            for(int j=i;j<N;j+=i)
            {
                if(!phi[j])
                    phi[j] = j;
                phi[j] = phi[j] / i * (i - 1);
            }
        }
    }
}

欧拉函数的和:phi_sum(n) = the sum of phi(i) where gcd(i,n) = 1 and 1 <= i <= n.

phi_sum(n) = n * phi(n) / 2 (n >= 2) .

phi_sum(n) = 1 (n == 1) .

抱歉!评论已关闭.