文章目录

  • 欧 拉 函 数 线 性 筛 欧拉函数线性筛 欧拉函数线性筛

相 关 性 质 : 相关性质 : 相关性质:

  • p h i [ 1 ] = 1 phi[1]=1 phi[1]=1.

  • p h i [ p ] = p − 1 phi[p]=p-1 phi[p]=p−1, ( p p p 为质数)

  • 若 p ∣ x p|x p∣x, <mtext>    </mtext> p h i [ x ∗ p ] = p h i [ x ] ∗ p \ \ phi[x*p]=phi[x]*p   phi[x∗p]=phi[x]∗p, 否则 p h i [ x ∗ p ] = p h i [ x ] ∗ ( p − 1 ) phi[x*p]=phi[x]*(p-1) phi[x∗p]=phi[x]∗(p−1).

证明有时间再填坑吧 …

红色字体可以记为: 无约减一/有余减一.

放出代码

		for(int i = 2; i < N; i ++)
                if(!sign[i]) prime[++num] = i, phi[i] = i - 1;
                for(int j = 1; i*prime[j] <= N && j <= num; j ++){
                        sign[i*prime[j]] = 1;
                        if(i % prime[j]) phi[i*prime[j]] = phi[i] * (prime[j]-1);
                        else{
                                phi[i*prime[j]] = phi[i] * prime[j];
                                break ;
                        }
                }

  • 欧 拉 函 数 相 关 欧拉函数相关 欧拉函数相关

<munder> ∑ d ∣ N </munder> φ ( d ) = N \sum_{d|N} \varphi(d) = N d∣N∑​φ(d)=N

证 明 : 证明 : 证明:

可以点击 这里

待填坑