积性函数

积性函数

概念：一个函数$f(x)$,满足存在一对$p$,$q$且$gcd(p,q)=1$,都有$f(pq)=f(p)f(q)$;那么这个函数就是积性函数

证明几个例子：

1、$f(x)=1$

$$证明-----------------------------\\常值函数f(pq)=1=1×1=f(p)f(q)$$

2、$f(x)=x$

$$证明----------------------------- \\ f(pq)=pq=f(p)f(q)$$

3、$f(x)=[x=1]$

$$证明-----------------------------\\ 当x=1，此时f（x）=1，否则f（x）=0 \\（一）当p或q为1时，f(pq)=f(q)或f(pq)=f(p) \\即此时，f(pq)=f(p)f(q) \\（二）当p和q都不为1时，f(pq)=0,f(q)=0,f(p)=0 \\即此时，f(pq)=0=f(p)f(q)$$

4、$f(n)=n(1-\frac{1}{p_1})(1-\frac{1}{p_2})…(1-\frac{1}{p_i})$ （欧拉函数：1…n中与n互质的数的数量）

$$证明--------------------------- \\由唯一分解定理(p_i,q_i表示)质数可得\\ p=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}....p_k^{\alpha_k}\\ q=q_1^{\alpha_1}q_2^{\alpha_2}q_3^{\alpha_3}....q_k^{\alpha_k}\\ 又∵gcd（p，q）=1 \\∴p_i与q_i不相等\\ ∴qp=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}....p_k^{\alpha_k}*q_1^{\alpha_1}q_2^{\alpha_2}q_3^{\alpha_3}....q_k^{\alpha_k} \\∴f(qp)=qp*(1-\frac{1}{p_1})*(1-\frac{1}{p_2})...(1-\frac{1}{p_i})*(1-\frac{1}{q_1})*(1-\frac{1}{q_2})...(1-\frac{1}{q_i})=f(q)f(p)$$

5、$f(n)=n的正因子的数量$

$$证明--------------------------- \\由唯一分解定理(p_i,q_i表示)质数可得\\ p=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}....p_k^{\alpha_k}\\ q=q_1^{\alpha_1}q_2^{\alpha_2}q_3^{\alpha_3}....q_k^{\alpha_k}\\ 又∵gcd（p，q）=1 \\∴p_i与q_i不相等\\ pq的正因子的数量=p的正因子的数量*q的正因子的数量（排列组合） \\即f（pq）=f（q）*f(p)$$

命题：如果$f(n),g(n)$为积性函数，则$h(n)=f(n)*g(n)$也是积性函数

如何计算积性函数？

（1）计算单点积性函数

设$f$为积性函数，假设$p=p_1^{\alpha_1}p_2^{\alpha_2}p_3^{\alpha_3}….p_k^{\alpha_k}$

则 $f(p)=f(p_1^{\alpha_1})f(p_2^{\alpha_2})f(p_3^{\alpha_3})….f(p_k^{\alpha_k})$

那么我可以类似质因数分解的方式来求解积性函数，大问题转化为小问题

int get_f(int n)
{
    int ans=1;
    for(int i=2;i<=n/i;i++)
    {
        int cnt=0;
        while(n%i==0){
            cnt++;
            n/=i;
        }
        ans*=f(i,cnt);
    }
    if(n>1)ans*=f(n,1);
    return ans;
}

（2）欧拉筛求一连串的积性函数

题目描述

求正整数 n的所有正因数的个数，q次询问。

输入描述:

第一行一个正整数 q (1≤q≤10e5) 。
第二行到第 q+1行，每行一个正整数 n (1≤n≤10e7)。

输出描述:

对于每个询问，输出一个正整数。两个答案间用空行分隔。

数据很大，直接上唯一分解定理时间复杂度为$O(q\sqrt{n})$,OJ评测机稍微不好直接寄 ！！！因此直接上直接上欧拉筛筛积性函数，时间复杂度$O(n)$

#include <iostream>
#include <algorithm>
#include <cmath>
using namespace std;
const int maxn = 1e7 + 10;
int f[maxn];
int cnt[maxn];//维护素数数量
int tot;//素数数量
bool not_prime[maxn];//判断是否为素数
int p[maxn];//素数表
int cal_f(int p, int a)//计算p^a有多少个正因子，直接排列组合
{
    return a+1;
}
void Eular()
{
    f[1] = 1;
    for (int i = 2; i <= maxn; i++)
    {
        if (!not_prime[i])
        {
            p[++tot] = i;
            f[i] = cal_f(i, 1);
            cnt[i]=1;//初始的当前素数为1
        }
        for (int j = 1; j <= tot && i * p[j] <= maxn; j++)
        {
            not_prime[i * p[j]] = 1;
            if (i % p[j] == 0)
            {
                cnt[i * p[j]] = cnt[i] + 1;
                f[i * p[j]] = f[i] / cal_f(p[j], cnt[i]) * cal_f(p[j], cnt[i] + 1);
                break;
            }
            cnt[i * p[j]] = 1;
            f[i * p[j]] = f[i]*cal_f(p[j],1);
        }
    }
}
int main()
{
    Eular();
    int q;
    cin >> q;
    while (q--)
    {
        int n;
        cin >> n;
        cout<<f[n]<<endl;
    }
    return 0;
}