欢迎您访问程序员文章站本站旨在为大家提供分享程序员计算机编程知识!
您现在的位置是: 首页  >  IT编程

欧拉函数

程序员文章站 2022-03-26 21:50:10
代码以后再补 欧拉函数 我们用$\phi(n)$表示欧拉函数 定义:$\phi(n)$表示对于整数$n$,小于等于$n$中与$n$互质的数的个数 性质 1.$\phi(n)$为积性函数 2.$\sum_{d|n}\phi(d)=n$ 3.$1$到$n$中与$n$互质的数的和为$n*\dfrac{\p ......

欧拉函数

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

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

性质

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

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

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

计算方法

$\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$中与其不互素的数为$1*p$,$2*p$....$p^{k-1}*p$,有$p^{k-1}$个

得证

 

当$k\neq 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<cmath>
#include<cstring>
#define LL long long 
using namespace std;
int main()
{
    LL N;
    while(cin>>N&&N!=0)
    {
        int limit=sqrt(N),ans=N;
        for(int i = 2; i <= limit ; ++i)
        {
            if(N%i==0) ans=ans/i*(i-1);
            while(N%i==0) N=N/i;
        }
        if(N>1) ans=ans/N*(N-1);
        printf("%d\n",ans);
    }
    return 0;
}

线性筛

因为欧拉函数是积性函数

因此可以使用线性筛法

性质1

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

证明:

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

性质2

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

则$\varphi \left( i*p\right) =\varphi \left( i\right) *\varphi \left( p\right)$

$=\varphi \left( i\ast p\right) =\varphi \left( i\right) \ast \left( p-1\right)$

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

性质3

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

则$\varphi \left( i\ast p\right) =\varphi \left( i\right) \ast p$

证明:

没怎么看懂,丢一个链接

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

#include<iostream>
#include<cstdio>
#include<cmath>
#include<cstring>
#define LL long long 
using namespace std;
const int MAXN=1e6+10;
int prime[MAXN],tot=0,vis[MAXN],phi[MAXN],N=10000;
void GetPhi()
{
    for(int i=2;i<=N;i++)
    {
        if(!vis[i])
        {
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(int j=1;j<=tot&&prime[j]*i<=N;j++)
        {
            vis[ i*prime[j] ] = 1; 
            if(i%prime[j]==0)
            {
                phi[ i*prime[j] ]=phi[i]*prime[j];
                break;
            }
            else phi[ i*prime[j] ]=phi[i]*(prime[j]-1);
        }
    }
}
int main()
{
    GetPhi();
    cin>>N;
    printf("%d\n",phi[N]);
    return 0;
}

 

例题

放两道水题

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

题解

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

题解