欧拉函数(复习自用笔记)

复习资料来源:刘汝佳.系列 欧拉函数描述为 ϕ ( n ) = 小 于 n 且 与 n 互 素 的 数 字 个 数 \phi(n)=小于n且与n互素的数字个数 ϕ(n)=小于n且与n互素的数字个数. 如 何 求 得 欧 拉 函 数 呢 , 首 先 运 用 容 斥 定 理 求 . 如何求得欧拉函数呢,首先运用容斥定理求. 如何求得欧拉函数呢,首先运用容斥定理求. n = p 1 a 1 ∗ p 2 a 2 . . p 3 a 3 n=p_1^{a1}*p_2^{a2}..p_3^{a3} n=p1a1​∗p2a2​..p3a3​ 那么先减去包含 p 1 , p 2 , p 3 p1,p2,p3 p1,p2,p3倍数的个数. n − ( n / p 1 ) − ( n / p 2 ) . . − ( n / p k ) n-(n/p1)-(n/p2)..-(n/p_k) n−(n/p1)−(n/p2)..−(n/pk​) 再加上同时包含 p 1 p 2 , p 1 p 3 , p 2 p 3.. 等 含 两 个 因 子 的 个 数 p1p2,p1p3,p2p3..等含两个因子的个数 p1p2,p1p3,p2p3..等含两个因子的个数 + ( n / ( p 1 ∗ p 2 ) ) + ( n / ( p 1 ∗ p 3 ) . . +(n/(p1*p2))+(n/(p1*p3).. +(n/(p1∗p2))+(n/(p1∗p3).. 然后再减去含有三个因子的个数… ϕ ( n ) = ∑ S ⊆ p 1 , p 2.. p k ( − 1 ) ∣ S ∣ ∗ n ∏ p i ⊂ s p i \phi(n)=\sum_{S\subseteq{p1,p2..pk}}(-1)^{|S|}*{n\over \prod_{pi\subset s}pi} ϕ(n)=∑S⊆p1,p2..pk​(−1)∣S∣∗∏pi⊂s​pin​. 紫书上提供的式子,看起来十分别扭,也难以计算. 考虑重新组合上述式子.实际上类似于二项式计算.可以认为每一个 p p p都是由 ( 1 − 1 p i ) 相 乘 组 合 而 成 (1-{1\over p_i})相乘组合而成 (1−pi​1​)相乘组合而成 所以有: ϕ ( x ) = n ∗ ∏ ( 1 − 1 p i ) \phi(x)=n*\prod(1-{1\over p_i}) ϕ(x)=n∗∏(1−pi​1​) 实际代码的时候需要我们把上述括号通分了再计算. ( p i − 1 ) p (pi-1) \over p p(pi−1)​,那么对于单个数字x的 ϕ ( x ) , 找 到 一 个 x % p = = 0 的 数 字 p , 直 接 让 n 包 含 p 的 因 子 全 部 去 除 , 这 样 我 们 保 证 了 , 每 次 找 到 一 个 p ， 必 然 是 唯 一 分 解 中 对 应 的 p . 因 为 我 们 每 次 找 到 一 个 p , 是 把 它 对 应 的 贡 献 全 部 去 掉 , 那 么 这 个 p 必 然 是 我 们 要 找 到 的 唯 一 分 解 的 p \phi(x),找到一个x\%p==0的数字p,直接让n包含p的因子全部去除,这样我们保证了,每次找到一个p，必然是唯一分解中对应的p.因为我们每次找到一个p,是把它对应的贡献全部去掉,那么这个p必然是我们要找到的唯一分解的p ϕ(x),找到一个x%p==0的数字p,直接让n包含p的因子全部去除,这样我们保证了,每次找到一个p，必然是唯一分解中对应的p.因为我们每次找到一个p,是把它对应的贡献全部去掉,那么这个p必然是我们要找到的唯一分解的p. 单个欧拉函数的计算,类似于试除法. 注意,我们是在枚举 n \sqrt{n} n ​范围内的素数,并没有讨论 n n n本身是素数的情况,那种情况我们放在函数末尾处理,即 x > 1 x>1 x>1的情况. 单个 ϕ ( x ) 的 计 算 情 况 \phi(x)的计算情况 ϕ(x)的计算情况

int phi(int x){
	int ans = n;//phi(x) = n / {(1-1/p1)*(1-1/p2)...} 
	for(int i=2;i1) ans = ans/n*(n-1); 
}

与素数筛法类似,我们也能以几乎线性的时间求出欧拉函数. 先给代码再解释原理:

void phi_table(int n){
	for(int i=2;i