积性函数相关

mod998244353 · 2021-03-11 18:01:42 · 个人记录

以下内容中，a|b表示a是b的因数，a\not|b表示a不是b的因数

前置知识：特别基础的数论

可能更好的阅读体验

积性函数

这部分设n质因数分解后为\prod\limits_{i=1}^kp_i^{c_i}

一些数论函数：

莫比乌斯函数：\mu(n)=\begin{cases}1\qquad n=1\\(-1)^k\qquad c_1=c_2=\cdots=c_k=1\\0\qquad\operatorname{otherwise}\end{cases}
欧拉函数（表示小于等于n且与n互质的数的个数）\varphi(n)=\begin{cases}1\qquad\qquad\qquad\qquad n=1\\n\prod\limits_{i=1}^k(1-\dfrac{1}{p_i})\qquad\operatorname{otherwise}\end{cases}
常函数：I(n)=1
单位函数：\epsilon(n)=[n=1]（若p成立则[p]是1，否则[p]为0）
恒等函数：id(n)=n
因数个数函数：d(n)=\sum\limits_{k|n}1
因数和函数：\sigma(n)=\sum\limits_{k|n}k
素因子个数函数：\Omega(n)=\sum\limits_{i=1}^kc_i
奇怪的函数\lambda(n)=(-1)^{\Omega(n)}
不同素因子个数函数：\omega(n)=k

积性函数：对于任意互质的两个数 a,b，满足 f(ab)=f(a)f(b)的函数

如\mu,\varphi,d,\sigma

完全积性函数：对于任意的两个数 a,b，满足 f(ab)=f(a)f(b)的函数

如I,\epsilon,id,\lambda

求欧拉函数和莫比乌斯函数

分解质因数，按照其定义和计算公式计算即可。

#include<bits/stdc++.h>
using namespace std;
int getphi(int n) {//phi
    int tmp=n,ans=n;
    for(int i=2; i*i<=tmp; ++i)
        if(!(tmp%i)) {//满足这个的每一个i都是质数，因为之前所有质因子都被除掉了 
            ans-=ans/i;//即ans=ans*(i-1)/i; 
            while(!(tmp%i))tmp/=i;
        }
    return tmp>1?ans-ans/tmp:ans;//最后一个质因数要判断 
}
int getmu(int n) {//mu
    int tmp=n,ans=1;
    for(int i=2; i*i<=tmp; ++i)
        if(!(tmp%i)) {
            ans=-ans;//乘上-1
            tmp/=i;
            if(!(tmp%i))//指数大于1
                return 0; 
        }
    return tmp>1?-ans:ans;//最后一个质因数的指数一定为1 
}
int n;
int main() {
    scanf("%d",&n);
    printf("%d %d\n",getphi(n),getmu(n));
    return 0;
}

欧拉函数和莫比乌斯函数的线性筛

bool isp[MAXN];
int prime[MAXN],pcnt;
void init(int n) {
    for(int i=2; i<=n; ++i) {
        if(!isp[i])prime[++pcnt]=i;//0
        for(int j=1,x; j<=pcnt&&(x=prime[j]*i)<=n; ++j) {
            isp[prime[j]*i]=1;
            if(!(i%prime[j]))break;//1
        }
    }
}

在上面的欧拉筛的代码中，0处判断i是否是质数，1处判断i,prime[j]是否互质了，那么我们可以通过这个部分进行线性筛欧拉函数和莫比乌斯函数。

根据两个函数的定义，当i为质数时，\varphi(i)=i-1,\mu(i)=-1

首先它们都是积性函数，所以没有break时，直接相乘即可。

根据莫比乌斯函数的定义，当i,prime[j]不互质时\mu(i\times prime[j])=0

当i,prime[j]不互质时，我们设x=i\times prime[j]分解质因数后为p_1^{k_1}p_2^{k_2}\cdots p_c^{k_c}（不妨设其中p_1=prime[j]，有k_1\geq2）则

\varphi(x)=p_1^{k_1-1}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_c^{k_c-1}(p_c-1)

\varphi(\dfrac{x}{p_1})=p_1^{k_1-2}(p_1-1)p_2^{k_2-1}(p_2-1)\cdots p_c^{k_c-1}(p_c-1)

可以发现\dfrac{\varphi(x)}{\varphi(\dfrac{x}{p_1})}=prime[j]

那就可以线性筛了

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef unsigned long long ull;
const int MAXN=6000500;
bool isp[MAXN+1];
int phi[MAXN+1],mu[MAXN+1],pcnt,n,prime[MAXN+1];
int main() {
    mu[1]=phi[1]=1;
    for(int i=2; i<=MAXN; ++i) {
        if(!isp[i]) {
            prime[++pcnt]=i;
            mu[i]=-1;
            phi[i]=i-1;
        }//素数时的值
        for(int j=1,x; j<=pcnt&&(x=i*prime[j])<=MAXN; ++j) {
            isp[x]=true;
            if(i%prime[j]) {
                mu[x]=-mu[i];
                phi[x]=phi[i]*(prime[j]-1);
            } else {
                mu[x]=0;
                phi[x]=phi[i]*prime[j];
                break;
            }//合数时的值
        }
    }
    return 0;
}

来几道题：

P2303 Longge 的问题

先用一个d枚举\gcd(i,n)

\sum\limits_{d|n}\sum\limits_{i=1}^n[\gcd(i,n)=d]d

提出d，将后面柿子的\gcd除以d

\sum\limits_{d|n}d\sum\limits_{i=1}^{\frac{n}{d}}[\gcd(i,\frac{n}{d})=1]

后面的部分其实就是\varphi(\dfrac{n}{d})

\sum\limits_{d|n}d\varphi(\dfrac{n}{d})

就可以计算了，时间复杂度O(\sqrt n)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll n,ans;
ll getphi(ll n) {
    ll tmp=n,ans=n;
    for(ll i=2; i*i<=tmp; ++i)
        if(!(tmp%i)) {
            ans-=ans/i;
            while(!(tmp%i))tmp/=i;
        }
    return tmp>1?ans-ans/tmp:ans;
}
int main() {
    scanf("%lld",&n);
    for(ll i=1,k; i*i<=n; ++i)
        if(!(n%i)) {
            k=n/i;
            ans+=getphi(k)*i;
            if(i^k)ans+=getphi(i)*k;
        }
    printf("%llu\n",ans);
    return 0;
}

P2158 仪仗队

我们可以假设C君的位置为(0,0)，建立一个平面直角坐标系。

那么队伍可以看做是一个(0,0)\rightarrow(n-1,n-1)的n\times n的矩阵。

我们可以不考虑(0,1)和(1,0)，最后在加上，就变成(1,1)\rightarrow(n-1,n-1)的(n-1)\times(n-1)的矩阵。

我们可以发现整个图形是对称的，所以只用算一半，乘上2，再减去重复计算的(1,1)，我们就来算满足b\leq a的那一半。

我们可以发现，对于一个点(a,b)，当\gcd(a,b)>1时，会被(\dfrac{a}{\gcd(a,b)},\dfrac{b}{\gcd(a,b)})挡住，例如(4,2)会被(2,1)挡住。（原理为相似三角形）

所以能看到的(a,b)都有\gcd(a,b)=1。

设f_a表示满足(a,b)能被看到的b有几个（1\leq b\leq a\leq n-1）。

则这一半的个数为\sum\limits_{a=1}^n f_a，整个的答案就是2(\sum\limits_{a=1}^n f_a)-1+2=2(\sum\limits_{a=1}^n f_a)+1。

由\gcd(a,b)=1,b\leq a得，f_a就是表示小于等于n且与n互质的数的个数，即\varphi(a)，那么我们就把\varphi线性筛出来再求和即可。

注意要特判n=1的情况

#include <bits/stdc++.h>
using namespace std;
const int MAXN=40005;
bool isp[MAXN];
int prime[MAXN],pcnt,phi[MAXN],ans;
void init(int n) {
    ans=phi[1]=1;
    for(int i=2; i<=n; ++i) {//线性筛phi
        if(!isp[i]) {
            prime[++pcnt]=i;
            phi[i]=i-1;
        }
        for(int j=1,x; j<=pcnt&&(x=prime[j]*i)<=n; ++j) {
            isp[prime[j]*i]=1;
            if(i%prime[j]) {
                phi[x]=phi[i]*phi[prime[j]];
            } else {
                phi[x]=phi[i]*prime[j];
                break;
            }
        }
        ans+=phi[i];//顺便求和
    }
}
int main() {
    int n,q;
    scanf("%d",&n);
    init(--n);
    printf("%d\n",n==0?0:ans*2+1);//特判0
    return 0;
}

P1390 公约数的和

设f_k为1\leq x<y\leq n且\gcd(x,y)=k有多少组。

可以得到答案为\sum\limits_{k=1}^nkf_k

接下来考虑求f_k

首先f_k可以写成\sum\limits_{i=1}^n\sum\limits_{j=i+1}^n[\gcd(i,j)=k]

对于\gcd(i,j)=k有\gcd(\dfrac{i}{k},\dfrac{j}{k})=1，我们就可以转换成：

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

把i,j都除以k：

\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{j=i+1}^{\lfloor\frac{n}{k}\rfloor}[\gcd(i,j)=1]

把j提到前面（对答案没有影响）

\sum\limits_{j=2}^{\lfloor\frac{n}{k}\rfloor}\sum\limits_{i=1}^{j-1}[\gcd(i,j)=1]

后面的\sum\limits_{i=1}^{j-1}[\gcd(i,j)=1]即是\varphi(j)（因为j>1）

所以f_k=\sum\limits_{j=2}^{\lfloor\frac{n}{k}\rfloor}\varphi(j)=\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\varphi(i)-1

所以原式=\sum\limits_{k=1}^nk(\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\varphi(i)-1)=\sum\limits_{k=1}^nk(\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\varphi(i))-k

括号内线性筛+前缀和预处理，直接O(n)求即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e7+100;
int phi[MAXN],cnt,n,prime[MAXN];
ll sum[MAXN],ans;
int main() {
    scanf("%d",&n);
    sum[1]=phi[1]=1;
    for(int i=2,p; i<=n; ++i) {//线性筛欧拉函数
        if(!phi[i])prime[++cnt]=i,phi[i]=i-1;
        for(int j=1; j<=cnt; ++j) {
            p=prime[j]*i;
            if(p>n)break;
            if(!(i%prime[j])) {
                phi[p]=phi[i]*prime[j];
                break;
            }
            phi[p]=phi[i]*(prime[j]-1);
        }
        sum[i]=sum[i-1]+phi[i];//欧拉函数的前缀和
    }
    for(int i=1; i<=n; ++i)
        ans+=sum[n/i]*i-i;
    printf("%lld\n",ans);
    return 0;
}

P2398 GCD SUM

和上题差不多，可以算是双倍经验。

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

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

可以发现前面两个都是上题要求的，后者就是\sum\limits_{i=1}^ni。

把上题的式子代进来：

\sum\limits_{i=1}^n\sum\limits_{j=1}^n\gcd(i,j)=2(\sum\limits_{k=1}^nk(\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\varphi(i))-k)+\sum\limits_{k=1}^nk=(\sum\limits_{k=1}^n2k(\sum\limits_{i=1}^{\lfloor\frac{n}{k}\rfloor}\varphi(i))-k)

这个是经典结论，可以记一下。

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const int MAXN=1e7+100;
int phi[MAXN],cnt,n,prime[MAXN];
ll sum[MAXN],ans;
int main() {
    scanf("%d",&n);
    sum[1]=phi[1]=1;
    for(int i=2,p; i<=n; ++i) {
        if(!phi[i])prime[++cnt]=i,phi[i]=i-1;
        for(int j=1; j<=cnt; ++j) {
            p=prime[j]*i;
            if(p>n)break;
            if(!(i%prime[j])) {
                phi[p]=phi[i]*prime[j];
                break;
            }
            phi[p]=phi[i]*(prime[j]-1);
        }
        sum[i]=sum[i-1]+phi[i];
    }
    for(int i=1; i<=n; ++i)
        ans+=((sum[n/i]<<1)-1)*i;
    printf("%lld\n",ans);
    return 0;
}