欧拉函数总结

本文移植自个人的原博客（原文）

欧拉函数的定义

$\varphi(n)$定义为$1$到$n$中与$n$互质的数的个数。

欧拉函数的求解

通项公式

$\varphi(n)=n(1−1/p_1)(1−1/p_2)…(1−1/p_{tot})$ (其中$p$为$n$的质因子，$tot$为质因子个数)

int euler_phi(int n)
{
    int m=(int)sqrt(n);
    int ans=n;
    for(int i=2;i<=m;i++)
    {
        if(n%i==0)
        {
            ans=ans/i*(i-1);
            while(n%i==0) n/=i;//与分解质因数相结合
        }
    }
    if(n>1) ans=ans/n*(n-1);
    return ans;
}

线性筛法

逆元一般通过线性筛法求解，该方法的时间复杂度为$O(n)$，可以预处理出前$n$项欧拉函数。

int prime[2*sqrt(N)+1],phi[N];

bool vis[N];

int tot;
int getprime()
{
    for(int i=2;i<=N;++i)
    {
        if(!vis[i])
        {
            prime[++tot]=i;
            phi[i]=i-1;
        }
        for(int t=1;t<=tot&&prime[t]*i<=N;++t)
        {
            vis[i*prime[t]]=true;
            if(i%prime[t]==0){phi[i*prime[t]]=phi[i]*prime[t];break;}
            phi[i*prime[t]]=phi[i]*(prime[t]-1);
        }
    }
}

相关习题

SDOI2008 沙拉公主的困惑

题目描述

大富翁国因为通货膨胀，以及假钞泛滥，政府决定推出一项新的政策：现有钞票编号范围为$1$到$N$的阶乘，但是，政府只发行编号与$M!$互质的钞票。房地产第一大户沙拉公主决定预测一下大富翁国现在所有真钞票的数量。现在，请你帮助沙拉公主解决这个问题，由于可能张数非常大，你只需计算出对$R$取模后的答案即可。$R$是一个质数。

输入第一行为两个整数$T,R$。$R<=10^9+10,T<=10000$，表示该组中测试数据数目，$R$为模数。

后面$T$行，每行一对整数$N,M$，见题目描述。

输出共$T$行，对于每一对$N,M$，输出$1$至$N!$中与$M!$素质的数的数量对$R$取模后的值。

对于$100 \ percent$的数据，$1 < = M < = N < = 10000000$

题解

题意明确$m<=n$，且易知$m!|n!$那么只需要算出$\varphi(m!)$即可，根据欧几里得算法可知最后的答案即为$\varphi(m!)∗n!/m!(modp)$

对于$\varphi(m!)$来说，$m!$的值过大，只能利用通项公式来求解，易知$m!$的所有质因数即为$1$到$m$中所有的质数，由于通项公式中涉及模运算下的除法，所以应先处理一下逆元。

#include<cstdio>
#include<iostream>
const int M = 1e6+1;
using namespace std;
bool vis[M+100];
long long prime[500500],ans[M+100],fac[M+100],rev[M+100];
int n,m,p,T,tot;
int main()
{
    scanf("%d%d",&T,&p);

    for(int i=2;i<=M;i++)
    {
        if(!vis[i])prime[++tot]=i;
        for(int j=1;j<=tot&&prime[j]*i<=M;j++)
        {
            vis[prime[j]*i]=1;
            if(i%prime[j]==0)
                break;
        }
    }
    fac[1]=1;
    for(int i=2;i<=M;i++)fac[i]=fac[i-1]*i%p;
    rev[1]=1;
    for(int i=2;i<=M&&i<p;i++)rev[i]=(p-p/i)*rev[p%i]%p;
    ans[1]=1;
    for(int i=2;i<=M;i++)
    {
        if(!vis[i])    ans[i]=ans[i-1]*(i-1)%p*rev[i%p]%p;
        else                ans[i]=ans[i-1];
    }
    while(T--)
    {
        scanf("%d%d",&n,&m);
        printf("%d\n",fac[n]*ans[m]%p);
    }
}