欧拉函数与积性函数

xishanmeigao · 2022-07-23 10:37:53 · 个人记录

# Part 1：欧拉函数及其性质 - **定义**：欧拉函数 $φ(n)$ 表示小于等于 $n$，且与 $n$ 互质的正整数的个数。 - **公式**：若在算数基本定理中，$n=p_1^{c_1}p_2^{c_2}...p_m^{c_m}$（$p$ 为质数），则由容斥原理： $$φ(n)=n*\dfrac{p_1-1}{p_1}*\dfrac{p_2-2}{p_2}*...*\dfrac{p_m-m}{p_m}=n*\prod\limits_{p\mid{n}}{(1-\dfrac{1}{p})}\qquad(p \in primes)$$ 关于此公式的证明，读者可自行推导 #### 一些性质 1. 若 $n$ 是质数，则 $φ(n)=n-1

若 n=p^k，且 p 为质数，则 φ(n)=(p-1)*p^{k-1}
若 p 是质数，且 \begin{cases}p\mid{n}&\Rightarrowφ(nq)=φ(n)*q\\p\nmid{n}&\Rightarrowφ(nq)=φ(n)*(q-1)\end{cases}
n=\sum\limits_{d\mid{n}}{φ(d)}
φ(ab)=φ(a)*φ(b)*\frac{d}{φ(d)}$，其中 $d=\gcd(a,b)

Part 2：积性函数

定义

若一个定义在正整数域上的函数 f，当 x,y 互质时，有 f(xy)=f(x)*f(y)，则称函数 f 是积性函数

特别地，当 x,y 不互质时仍有 f(xy)=f(x)*f(y) 的函数称为完全积性函数

常见完全积性函数：

ϵ(n)=[n=1]
I(n)=1
id_k(n)=n^k

常见积性函数

欧拉函数 \varphi(n)
莫比乌斯函数 \mu=I^{-1}
除数函数 \sigma_k(n)=\sum\limits_{d\mid n}d^k
除数函数 d(n)= n 的约数个数

一些乘积结论

\mu(ij)=[i\perp j]\mu(i)\mu(j)
φ(ab)=φ(a)*φ(b)*\frac{d}{φ(\gcd(a,b))}
d(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y]
\sigma_k(ij)=\sum\limits_{x|i}\sum\limits_{y|j}[x\perp y](\frac{xj}{y})^k

除数函数的计算

对于 n=p_1^{c_1}p_2^{c_2}\dots p_m^{c_m}，有：

d(n)=(c_1+1)(c_2+1)\dots(c_m+1)
记 p 为 n 的最小质因子，有：
d(n)=\begin{cases}2d(n/p)-d(n/p^2)&p^2\mid n\\2d(n/p)&\rm otherwise\end{cases}
\sigma_k(n)=\prod\limits_{i=1}^m(1+p_i+p_i^2+\dots+p_i^{c_i})

Part 3：欧拉函数例题

【模板题】求 φ(n)

解题思路

我们已知 φ(n) 的计算公式，所以只需对 n 进行质因数分解即可

代码

#include<bits/stdc++.h>
using namespace std;

const int N=100001;

int n;

int GetPhi(int n)
{
    int ans=n;
    for(int i=2; i*i<=n; i++) //分解质因数
    {
        if(n%i==0)
        {
            ans=ans*(i-1)/i; //计算公式
            while(n%i==0)
                n/=i;
        }
    } 

    if(n>1) //还剩下一个较大的质数
        ans=ans*(n-1)/n;

    return ans; 
}

int main()
{
    cin>>n;
    cout<<GetPhi(n);

    return 0;
}

【模板题】求 φ(1) ~ φ(n)

解题思路

由于欧拉函数是积性函数，所以我们考虑用线性筛求解
从欧拉函数性质 3 出发，在线性筛中，每个合数 x 都会被它最小的质因子 p 筛去，此时我们就可以用 p (或 p-1) 和 φ(x/p) 来推出 φ(x) ，具体是 p 还是 p-1，要看 x/p，即我们外层循环的 i 是否是 q 的倍数；而对于每个质数 y，由性质 1 可得：φ(y)=y-1

代码

#include<bits/stdc++.h>
using namespace std;

const int N=100001;

int n,phi[N],v[N],prime[N],tot;

void GetPhi(int n)
{
    phi[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(!v[i])
        {
            v[i]=i;
            prime[++tot]=i;
            phi[i]=i-1;
        }

        for(int j=1; j<=tot; j++)
        {
            if(prime[j]>v[i] || prime[j]>n/i)
                break;
            v[i*prime[j]]=prime[j];
            if(i%prime[j]==0)
                phi[i*prime[j]]=prime[j]*phi[i];
            else
                phi[i*prime[j]]=(prime[j]-1)*phi[i];
        } 
    }
}

int main()
{
    cin>>n;

    GetPhi(n);

    for(int i=1; i<=n; i++)
        cout<<phi[i]<<" ";

    return 0;
}

【练习题】公约数的和

（题目传送门）

题目大意

给定 n，求

\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j)

其中 \gcd(i, j) 表示 i 和 j 的最大公约数。

解题思路

我们记 ans=\sum\limits_{i = 1}^n \sum\limits_{j = i + 1}^n \gcd(i, j)
改写一下可得：
ans=\dfrac{\sum\limits_{i = 1}^n \sum\limits_{j =1}^n \gcd(i, j)-\sum\limits_{i=1}^n\gcd(i,i)}{2} =\dfrac{\sum\limits_{i = 1}^n \sum\limits_{j =1}^n \gcd(i, j)-\sum\limits_{i=1}^ni}{2}
那么我们枚举最大公约数 d，设 f(d) 表示有多少对 (i,j) 使得 \gcd(i,j)=d，那么就有
ans=\dfrac{\sum\limits_{d=1}^n{d*f(d)} -\sum\limits_{i=1}^ni}{2}
进一步思考，若整数对 (i,j) 满足 \gcd(i,j)=d，则有：i\mid d,\: j\mid d,\:\gcd(i/d,j/d)=1。
设 x=i/d,\:y=j/d，下面分 3 种情况讨论对于每一个 x，有多少个 y 满足 \gcd(x,y)=1：

1、若 i>j，则 x>y。又因为 j<i \leqslant n，所以 y<x \leqslant n/d。那么满足 \gcd(x,y)=1 的 y 的数量就为 1 ~ x 里与 x 互质的数的个数，即 φ(x)。

2、若 i<j，则 x<y，那么令 x'=y,\:y'=x，那么此时的答案即为第 1 种情况中已求出的满足 \gcd(x',y')=1 的 y 的数量。所以答案为 φ(x')。因此，每一个 φ(x) 都会被算 2 遍

3、若 i=j，则 x=y，此时 y 的取值很明显只有 1 种
综上，
f(d)=(\sum\limits_x^{n/d}{φ(x)})*2+1
在求 f(d) 前，可对 φ() 进行前缀和的预处理，节省时间

代码

#include<bits/stdc++.h>
using namespace std;

const int N=2000010;

int n,phi[N],v[N],prime[N],tot;
long long ans,sum[N],f[N];

void GetPhi(int n) //求phi[1~n]
{
    phi[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(!v[i])
        {
            v[i]=i;
            prime[++tot]=i;
            phi[i]=i-1;
        }

        for(int j=1; j<=tot; j++)
        {
            if(prime[j]>v[i] || prime[j]>n/i)
                break;
            v[i*prime[j]]=prime[j];
            if(i%prime[j]==0)
                phi[i*prime[j]]=prime[j]*phi[i];
            else
                phi[i*prime[j]]=(prime[j]-1)*phi[i]; 
        } 
    }

    for(int i=1; i<=n; i++) //前缀和预处理
        sum[i]=sum[i-1]+(long long)phi[i]; 
}

int main()
{   
    cin>>n;

    GetPhi(n);

    for(int i=1; i<=n; i++)
        f[i]=sum[n/i]*2-1,ans+=f[i]*(long long)i; //求f和ans

    ans=(ans-(long long)(1+n)*n/2)/2; //最后一步

    cout<<ans;

    return 0;
}

【练习题】GCD(x,n)>=m

题目大意

给定整数 n 和 m，问题是求有多少个整数 x，满足 1 \leqslant x \leqslant n 且 \gcd(x,n) \geqslant m。

解题思路

记 \gcd(x,n)=d，那么由定义得：d \mid n 。因此我们考虑去枚举 n 的约数，并舍去其中小于 m 的约数，那么剩下的数便可以作为 d 的取值。
对于大于等于 m 的约数 i，由上一题的解题思路可知：x\mid i 且 \gcd(x/i,n/i)=1，所以答案便为 φ(n/i)

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

int T,n,m;
LL ans;

LL GetPhi(int n) //求phi[n]
{
    LL ans=(LL)n;
    for(int i=2; i*i<=n; i++)
    {
        if(n%i==0)
        {
            ans=ans*(LL)(i-1)/i;
            while(n%i==0)
                n/=i;
        }
    } 

    if(n>1)
        ans=ans*(LL)(n-1)/n;

    return ans; 
}

int main()
{
    scanf("%d",&T);
    while(T--)
    {
        scanf("%d%d",&n,&m);
        ans=0;

        for(int i=1; i*i<=n; i++) //枚举约数
        {
            if(n%i==0)
            {
                if(i>=m) //约数i
                    ans=ans+(LL)GetPhi(n/i);
                if(i!=n/i && n/i>=m) //由于约数成对出现,所以n/i也是n的约数,注意要避免完全平方数的情况
                    ans=ans+(LL)GetPhi(i);
            }
        }

        printf("%lld\n",ans);
    }

    return 0;
}

【练习题】非互质数求和

题目大意

如果一个正整数 x 小于 n，而且 x 与 n 不互质，那么整数 x 称为“好数”。

给定一个正整数 n，求所有的“好数”的和。

这里互质的定义：如果 A,B 除 1 外没有其他的公因数，则称 A 与 B 互质。

答案模 1000000007。

解题思路

考虑到正面求解较难，我们可以考虑求答案的补集，即求所有与 n 互质的数的和
在这我们先引入一个结论：
\gcd(n,x)=\gcd(n,n-x)
这个结论我们最后会来证明。

那么如果 x 与 n 互质，由结论就可知 n-x 也与 n 互质
设集合 X 为与 n 互质的数的集合。则集合元素个数为 φ(n)，集合元素分别为 x_1,x_2\:......\:x_{φ(n)}。由刚刚的结论可知 x_i+x_{φ(n)-i+1}=n，这样的数对共有 φ(n)/2 个，所以 \sum\limits_{i=1}^{φ(n)}{x_i}=\dfrac{n*φ(n)}{2}
最后答案即为 \sum\limits_{i=1}^{n-1}{i}-\dfrac{n*φ(n)}{2}

关于引入结论的证明

设 d=\gcd(n,x)，则有 n=k_1d,\:x=k_2d 且 \gcd(k_1,k_2)=1 \quad (k_1,k_2 \in \mathbb{N^*})，那么 n-x=(k_1-k_2)d
假设 \gcd(n,n-x) \ne d，则 \gcd(k_1,k_1-k_2) \ne 1。所以可设 k_1=ab,k_1-k_2=ac\ (a\ne 1,\quad a,b,c \in \mathbb{N^*})，那么可推出 k_2=a(b-c)，易知 b-c \ne 0，所以 \gcd(k_1,k_2) \ne 1，因此假设矛盾
综上，\gcd(n,x)=\gcd(n,n-x)

代码

#include<bits/stdc++.h>
using namespace std;

const long long MOD=1000000007;

long long n; 

long long GetPhi(long long m)  //求phi[n]
{
    long long ans=m;
    for(int i=2; i*i<=m; i++)
    {
        if(m%i==0)
        {
            ans=ans*(i-1)/i;
            while(m%i==0)
                m/=i;
        }
    }

    if(m>1)
        ans=ans*(m-1)/m; 

    return ans;
}

int main()
{
    while(scanf("%lld",&n))
    {
        if(n==0)
            break;

        printf("%lld\n",(n*(n-1)/2-n*GetPhi(n)/2)%MOD);
    }

    return 0;
}

【练习题】USB的数学题

题目大意

求 F(n)=\sum\limits_{i=1}^n{\dfrac{n}{\gcd(i,n)}} 的值

#### 解题思路 - 设 $d=\gcd(i,n)$，则满足 $\gcd(i,n)=d$ 的 $i$ 的个数就为 $φ(n/d)$。所以 $F(n)$ 可写成 $$F(n)=\sum\limits_{d\mid n}^{}{φ(d)*d}$$ - 再看一眼数据范围，显然对于每组测试数据的每个 $n$，都进行根号级别的枚举是无法拿到满分的，所以我们要思考 $F(n)$ 所具有的其它性质——没错，积性函数！ - $F$ 是积性函数是很好证明的。设 $x,y$ 为互质的两个正整数。则 $F(x)=\sum\limits_{a\mid x}^{}{(φ(a)*a)},\:F(y)=\sum\limits_{b\mid y}^{}{(φ(b)*b)}$。那么 $F(x)*F(y)=\sum\limits_{a\mid x}^{}{(φ(a)*a)}*\sum\limits_{b\mid y}^{}{(φ(b)*b)}\:$。由于 $x$ 与 $y$ 互质，所以 $a$ 与 $b$ 也是互质的，再加上 $φ$ 是积性函数，所以 $$F(x)*F(y)=\sum\limits_{ab\mid xy}^{}{φ(ab)*ab}=F(xy)$$ 因此，$F$ 是积性函数 - 一开始我们已经说过，所有的积性函数都可以用**线性筛**求解。本题我们分 $3$ 种情况对 $F$ 的递推进行讨论： 1、当 $n=10$ 时，$10$ 的最小质因子为 $2$，$2$ 与 $10/2=5$ 互质，所以 $F(10)$ 可以由 $F(2)*F(5)$ 得到。这是最简单的一种情况。 2、当 $n=12$ 时，$12$ 的最小质因子为 $2$，但 $2$ 与 $12/2=6$ 不互质，所以此时无法直接递推。因为 $12=2^2*3$，所以我们需要令 $a=2^2,\:b=3$，这样 $a$ 与 $b$ 一定是互质的，再通过 $F(a)*F(b)$ 得到 $F(12)$。因此，我们需要记录每一个数的最小质因子的最高次幂的值，记为 $highPow[n]$。对于这种情况，我们就可以令 $a=highPow[n],b=n/a$，再通过 $F(a)*F(b)$ 得到 $F(n)

3、当 n=8 时，a=highPow[8]=8,\:b=8/a=1，就会产生 F(8)=F(8)*F(1) 这样的情况，所以我们还需要记录 n 的最小质因子的指数，记为 mi[n]。那么当 n=x^{mi[n]} 时，我们可以暴力求解 F(n)=\sum\limits_{d\mid n}^{}{φ(d)*d}\:。显然我们有 F(n)=\sum\limits_{i=1}^{mi[n]}{x^i*φ(x^i)}+1\: (+1是当 d=1 的情况)。由 φ 的计算公式，我们就可以得到：

F(n)=\sum\limits_{i=1}^{mi[i]}{x^i*x^i*(1-\dfrac{1}{x})}+1

=\sum\limits_{i=1}^{mi[i]}{x^i*x^i*(\dfrac{x-1}{x})}+1

=\sum\limits_{i=1}^{mi[i]}{x^i*x^{i-1}*(x-1)}+1

我们再通过一个简单的前缀积处理，就可以暴力的求解这种情况的 F(n)

代码

#include<bits/stdc++.h>
#define LL long long
using namespace std;

const int N=10000010;

int T,n;
int v[N],prime[N],tot;
LL f[N],highPow[N],mi[N],tmp[N];

void prework(int n)
{
    f[1]=1;
    for(int i=2; i<=n; i++)
    {
        if(!v[i])
        {
            v[i]=i;
            prime[++tot]=i;
            f[i]=(LL)(i-1)*i+1;
            highPow[i]=i;
            mi[i]=1;
        }

        for(int j=1; j<=tot; j++)
        {
            if(prime[j]>v[i] || prime[j]>n/i)
                break;

            int x=i*prime[j];
            v[x]=prime[j];

            if(i%prime[j]!=0) //第1种情况(由于prime[j]是质数,所以i与prime[j]互质当且仅当i不是prime[j]的倍数或约数)
            {
                highPow[x]=prime[j];
                mi[x]=1;
                f[x]=f[i]*f[prime[j]];
            }
            else
            {
                highPow[x]=highPow[i]*prime[j];
                mi[x]=mi[i]+1;

                int a=highPow[x],b=x/a;
                if(b==1) //第3种情况
                {
                    tmp[0]=1;
                    for(int i=1; i<=mi[x]; i++)
                        tmp[i]=tmp[i-1]*(LL)prime[j]; //前缀积处理prime[j]的幂
                    for(int i=1; i<=mi[x]; i++)
                        f[x]+=tmp[i]*tmp[i-1]*(LL)(prime[j]-1); //暴力求解
                    f[x]++; //加上d=1的情况
                }
                else //第2种情况
                    f[x]=f[a]*f[b];
            }
        } 
    }
}

int main()
{
    prework(N-10);

    scanf("%d",&T);
    while(T--)
    {
        scanf("%d",&n);
        printf("%lld\n",f[n]);
    }

    return 0;
}