【acm】【数论】欧拉定理与欧拉函数

duadua

发布于 2022-10-31 14:28:06

6340

发布于 2022-10-31 14:28:06

文章被收录于专栏：duadua blogduadua blog

欧拉定理

定义

证明

欧拉定理的证明与费马小定理的证明类似，需要以下引理。

tips

此引理的证明使用反证法即可。

下证欧拉定理。

欧拉函数

定义

上面所提及的

即为欧拉函数，表示小于m且与m互素的正整数的个数。

其有以下计算公式。

证明

欧拉函数可由由积性函数的性质得出。

证明所需要引理。

引理2 对一切正整数n, 有

实现

给定整数n，求得其欧拉函数的一个实现如下。

// 求单个整数的欧拉函数
int Euler(int x) {
    int ans = x, m = (int)sqrt(x*1.0)+1;
    for(int i = 2; i < m; ++i) if(x%i == 0) {
        ans = ans / i * (i-1);
        while(x%i == 0) x /= i;
    }
    if(x > 1) ans = ans / x * (x-1);
    return ans;
}

//递推求[1, n]的欧拉函数值phi[i]
void PhiTable(int n, int* phi) {
    for(int i = 1; i <= n; ++i) phi[i] = i;
    for(int i = 2; i <= n; i += 2) phi[i] /= 2;
    for(int i = 3; i <= n; i += 2) if(phi[i] == i) {    //i是质数
        for(int j = i; j <= n; j += i) {
            phi[j] = phi[j] / i * (i-1);                //i是j的一个因子
        }
    }
}