欧拉

· · 个人记录

欧拉函数：phi(x):在1~x中与x互质的数的个数

求法：

欧拉筛：

    b[1]=1;
    for(int i=2;i<=n;i++)
    {
        if(!b[i]) v[++k]=i,phi[i]=i-1;//质数的phi等于他减一
        for(int j=1;j<=k;j++)
        {
            if(i*v[j]>n) break;
            b[i*v[j]]=1;
            if(i%v[j]==0) 
            {
                phi[i*v[j]]=phi[i]*v[j];//i%p==0,phi(i*p)=phi(i)*p
                break;
            }
            else phi[i*v[j]]=phi[i]*phi[v[j]];//i%p!=0,phi(i*p)=phi(i)*phi(p)
        }
    }

单个求（n^1/2）

    for(int i=2;i*i<=m;i++)
    {
        if(m%i==0)
        {
            phi=phi/i*(i-1);
            while(m%i==0) m/=i;
        }
    }

//phi(x)=∏(x%pi==0)(pi-1)/pi

欧拉定理：

x与p互质：x^phi(p)≡1(%p)

感性证明：

令ai为所有<p与p互质的数

设pi=ai*x

引理1：

i!=j->pi≠pj (%p) (因为ai两两不同）

引理2：

gcd(pi%p,p)=1 (x,ai均与p互质）

所以，pi%p只有phi种取值

总证明：

因为pi%p只有phi种不同取值，而pi%p两两不同，且与p互质

所以，一个pi%p对应一个ai

所以∏pi≡∏ai(%p)

x^phi(p)*∏ai≡∏ai(%p0

x^phi(p)≡1(%p)

扩展欧拉：

当b>phi(p)时：

a^b≡a^(b%phi(p)+phi(p)) (%p)