数论知识总结-欧拉函数

NOIP爆零の辣鸡第一次学数论，啃腚有错误。。。所以这篇博客很可能是错的。。。墙裂推荐这个

定义

定义:小于等于n且与n互质的数的个数。

(phi(n)=sum_{i=1}^{n}[gcd(i,n)=1])

求法

求法1：只求(phi(n))

从(1)到(sqrt{n})枚举质因子。（我也不知道为什么是对的额饿哦呃俄鹅娥厄鄂讹蛾

好像是先分解(n=p_1^{k_1} p_2^{k_2} ... p_q^{k_q})，(phi(n)=n imes(1-frac{1}{p_1})(1-frac{1}{p_2})...(1-frac{1}{p_q}))

然后变一下(phi(n)=n imesprod_{k|n}{frac{k-1}{k}})

(O(sqrt{n}))

int euler(int n){
	int ret=n,m=n;
	for(rg int i=2;i*i<=m;++i){
		if(m%i==0)ret=ret/i*(i-1);
		while(m%i==0)m/=i;
	}
	if(m>1)ret=ret/m*(m-1);//n最多有一个大于sqrt(n)的质因子（又一句废话
	return ret;)
}

求法2：求(phi(2),phi(3),phi(4),...,phi(n))

需要枚举每一个质数的贡献。

所以一边筛质数一边求(phi)。

几乎是线性的。(O(nloglog n))

for(int i=2;i<=n;++i)phi[i]=i;
for(int i=2;i<=n;++i)
	if(phi[i]==i)for(rg int j=i;j<=n;j+=i)phi[j]=phi[j]/i*(i-1);

一些性质

若(p)为质数：(phi(n)=n-1)，(phi(p^{k})=(p-1) imes p^{k-1})
(sum_{i=1}^{n}[gcd(i,n)=1] imes i（小于等于n且与n互质的数之和）=sum_{i=1}^{n}[gcd(i,n)=1] imes (n-i)=frac{phi(n) imes n}{2})
欧拉函数是鸡积性函数（积性函数是啥。。。
(phi(n))都是偶数（除了(n=2)的情况）
(sum_{d|n}phi(d)=n)
(n)为奇数时，(phi(2n)=phi(n))

一些证明

(phi(n)=n-1)：显然。
(phi(p^{k})=(p-1) imes p^{k-1})：根据(phi(n)=n imes(1-frac{1}{p_1})(1-frac{1}{p_2})...(1-frac{1}{p_q}))，此时(q=1,p_1=p)，(phi(n)=n imesfrac{p-1}{p}=(p-1) imes p^{k-1})
第一个等号：
需要证明，(如果gcd(i,n)=1,1<=i<=n，则gcd(i,n-i)=1)
很容易啊。。。反证就是了
(如果gcd(i,n)=1,1<=i<=n，gcd(i,n-i)>1)
设(i=kx,n-i=ky [gcd(x,y)=1,k>1])，则(n=k(x+y))，显然GG
还要证明，(如果gcd(i,n)>1,1<=i<=n，则gcd(i,n-i)>1)
反证就是了，不写了。
第二个等号：
既然证完了第一个等号那就把他俩加起来
(sum_{i=1}^{n}[gcd(i,n)=1] imes i+sum_{i=1}^{n}[gcd(i,n)=1] imes (n-i)=sum_{i=1}^{n}[gcd(i,n)=1] imes n=phi(n) imes n)
emmmm证毕，除个2就行了
QAQ
根据2推一推
某博客里说要用到莫比乌斯反演。。。
将(n)和(2n)分别代进(phi(n)=n imes(1-frac{1}{p_1})(1-frac{1}{p_2})...(1-frac{1}{p_q}))即可。

一些例板子题

嗯，基本是看题解写的。

HDU2588

(gcd(i,n)>=m,1<=i<=n)，求(i)的个数。

首先设(n=kx,i=ky（x,y互质，显然x>=y）)

(gcd(i,n)=k)，我们需要求(k>=m)的个数。枚举这个k。

枚举k之后，x就确定了，y要满足(x,y互质且y<=x)，显然y的个数为(phi(x))。

然后依然是(O(n))。。。

可以折半枚举。点开上面那个博客去看吧。。。

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
typedef long long ll;
il int gi(){
    rg int x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
il int euler(int n){
    int ret=n,m=n;
    for(rg int i=2;i*i<=m;++i){
        if(m%i==0)ret=ret/i*(i-1);
        while(m%i==0)m/=i;
    }
    if(m>1)ret=ret/m*(m-1);
    return ret;
}
int main(){
#ifdef xzz
    freopen("in.in","r",stdin);
    freopen("out.out","w",stdout);
#endif
    int T=gi(),n,m,ans;
    while(T--){
        n=gi(),m=gi();ans=0;
        for(rg int s=1;s*s<=n;++s)
            if(n%s==0){
                if(s>=m)ans+=euler(n/s);
                if(n/s>=m&&s*s!=n)ans+=euler(s);
            }
        printf("%d
",ans);
    }
    return 0;
}

HDU 3501

嗯，见上面性质2及证明2

HDU 1286

嗯，见上面求法2

HDU 233333333

没了。

BZOJ2818

首先假装(x>=y)。

设(gcd(x,y)=k)，则(x=ak,y=bk(a,b互质，且a>=b))

枚举质数k，算出(1<=x<=lfloor n/k floor)

// It is made by XZZ
#include<cstdio>
#include<algorithm>
#define il inline
#define rg register
#define vd void
#define sta static
typedef long long ll;
il int gi(){
    rg int x=0,f=1;rg char ch=getchar();
    while(ch<'0'||ch>'9')f=ch=='-'?-1:f,ch=getchar();
    while(ch>='0'&&ch<='9')x=x*10+ch-'0',ch=getchar();
    return x*f;
}
ll phi[10000001];
bool isprime[10000001];
int main(){
    int n=gi();
    for(rg int i=1;i<=n;++i)phi[i]=i;
    for(rg int i=2;i<=n;++i)
        if(phi[i]==i){
            isprime[i]=1;
            for(rg int j=i;j<=n;j+=i)
                phi[j]=phi[j]/i*(i-1);
        }
    for(rg int i=1;i<=n;++i)phi[i]+=phi[i-1];
    ll ans=0,orz=0;
    for(rg int i=2;i<=n;++i)if(isprime[i])ans+=phi[n/i],++orz;
    printf("%lld
",ans*2-orz);
    return 0;
}

写完了。

吐血。。。