欧拉函数详解

欧拉函数

我们用$phi(n)$表示欧拉函数

定义:$phi(n)$表示对于整数$n$,小于等于$n$中与$n$互质的数的个数

性质

1.$phi(n)$为积性函数

证明:

此处证明需要用到下面计算方法1中的内容,建议先看后面再回过头来看这里

假设存在$p,q$,且$p*q=n$

将$n,p,q$进行质因数分解

$n=a_1^{p_1}a_2^{p_2}...a_k^{p_k}$

$p=a_1^{p_1}a_2^{p_2}...a_m^{p_m}$

$q=a_{m+1}^{p_{m+1}}a_{m+2}^{m+2}...a_k^{p_k}$

那么

$varphi left( nright) =nprod ^{k}{i=1}left( 1-dfrac {1}{p{i}}right)$

$varphi left( aright) =aprod ^{m}{i=1}left( 1-dfrac {1}{p{i}}right)$

$varphi left( bright) =bprod ^{k}{i=m+1}left( 1-dfrac {1}{p{i}}right)$

因为$n=a*b$

显然

$varphi left( nright) =varphi left( aright) varphi left( bright)$

这种方法也是常见的证明一个函数是积性函数的方法

2.$sum_{d|n}phi(d)=n$

3.$1$到$n$中与$n$互质的数的和为$n*dfrac{phi(n)}{2}(n>1)$

证明:若$gcd(n, i) = 1$,那么$gcd(n, n - i) = 1$

因此与$n$互质的数都是成对出现的。且每一对的和都为$n$

这样最终答案为$n * frac{phi(n)}{2}$

  1. $a^{phi(n)} equiv 1 pmod n$

欧拉函数详解

计算方法

$sqrt(n)$计算单值欧拉函数

假设我们需要计算$phi(n)$

分情况讨论

1.当$n=1$时

很明显,答案为$1$

2.当$n$为质数时

根据素数的定义,答案为$n-1$

(仅有$n$与$n$不互质)

3.当$n$为合数时

我们已经知道了$n$为素数的情况

不妨对$n$进行质因数分解

设$n=a_1^{p_1}a_2^{p_2}...a_k^{p_k}$

假设$k=1$

那么$phi(p^k)=p^k-p^{k-1}$

证明:

考虑容斥,与一个数互素的数的个数就是这个数减去与它不互素的数的个数

因为$p$是素数,所以在$p^k$中与其不互素的数为$1p$,$2p$....$p^{k-1}*p$,有$p^{k-1}$个

得证

当$kneq 1$时

$$phi(n)$$

$$=varphi left( a^{p_{1}}{1}a^{p{2}ldots }{2}a^{Pk}{k}right)$$

$$=prod ^{k}{i=1}a^{P_i}-a^{P{i}-1}_{i}$$

$$=prod ^{k}{i=1}a^{Pi}{i}(1-dfrac {1}{p_{i}})$$

$$=n*prod ^{k}{i=1}(1-dfrac {1}{p{i}})$$

#include<iostream>
#include<cstdio>
#include<cstring>
#include<algorithm>
using namespace std;
const int MAXN = 1e7 + 10;
int p, ans = 1, N;
void GetPhi() {
    for(int i = 2; i * i <= p; i++) {
        if(p % i == 0) {
            int now = i - 1; p /= i;
            while(p % i == 0) now = now * i, p /= i;
            ans = ans * now;
        }
    }
    if(p != 1) ans *= (p - 1); 
}
int main() {
    cin >> p; N = p;
    GetPhi();
    cout << ans;
    return 0;
}

线性筛

因为欧拉函数是积性函数

因此可以使用线性筛法

性质1

若$p$为素数,则$varphi left( pright) =p-1$

证明:

在$1-p$中,只有$(p,p)neq1$

性质2

若$i mod p neq 0$,且$p$为素数

则$varphi left( ipright) =varphi left( iright) varphi left( pright)$

$=varphi left( iast pright) =varphi left( iright) ast left( p-1right)$

这一步同时利用了性质1和欧拉函数的积性

性质3

若$i mod p = 0$,且$p$为素数,

则$varphi left( iast pright) =varphi left( iright) ast p$

证明:

没怎么看懂,丢一个链接

http://blog.csdn.net/Lytning/article/details/24432651

#include<bits/stdc++.h>
using namespace std;
const int MAXN = 3e5 + 10;
void GetPhi(int N) {
    static int phi[MAXN], vis[MAXN], prime[MAXN], tot = 0;
    for(int i = 2; i <= N; i++) {
        if(!vis[i]) prime[++tot] = i, phi[i] = i - 1;
        for(int j = 1; j <= tot && i * prime[j] <= N; j++) {
            vis[i * prime[j]] = 1;
            if(!(i % prime[j])) {phi[i * prime[j]] = phi[i] * prime[j]; break;}
            else phi[i * prime[j]] = phi[i] * (prime[j] - 1);
        }
    }
    while(cin >> N) cout << phi[N] << endl;
}
int main() {
    GetPhi(100);
    return 0;
}

例题

放几道水题

http://poj.org/problem?id=2407

题解

http://poj.org/problem?id=2478

题解

https://www.luogu.org/problemnew/show/P2158

题解

参考资料

数论学习笔记 欧拉函数 (一些性质和运用)内置杜教筛

原文链接: https://www.cnblogs.com/zwfymqz/p/8215259.html

欢迎关注

微信关注下方公众号,第一时间获取干货硬货;公众号内回复【pdf】免费获取数百本计算机经典书籍

原创文章受到原创版权保护。转载请注明出处:https://www.ccppcoding.com/archives/268498

非原创文章文中已经注明原地址,如有侵权,联系删除

关注公众号【高性能架构探索】,第一时间获取最新文章

转载文章受原作者版权保护。转载请注明原作者出处!

(0)
上一篇 2023年2月14日 下午7:23
下一篇 2023年2月14日 下午7:24

相关推荐