积性函数

你的名字 2023-03-01 05:47 108阅读 0赞

搞这个之前需要学习一个简单的知识——整除分块

参考博客链接：[https://blog.csdn.net/beautiful\_CXW/article/details/83143756][https_blog.csdn.net_beautiful_CXW_article_details_83143756]

首先它是用于求![20200722164838232.png][]

举个k为10的例子，看k/i的规律

![在这里插入图片描述][70]

把k/i为相同数值的放到一块，然后就看得懂板子了

typedef long long ll;
    int main() {
        ll n,k;
        scanf("%lld%lld",&n,&k);
        ll ans=0;
        for(ll l=1,r;l<=n;l=r+1) {
            if(k/l!=0) r=min(k/(k/l),n); 
            else r=n;
            ans+=(k/l)*(r-l+1)*(l+r)/2;
        }
        printf("%lld",ans);
        return 0;
    }

**如果f(1)=1 且 若x,y互质 f(x\*y)=f(x)\*f(y) 则成为积性函数**

**如果不要求x,y互质的话就是完全积性函数**

常见积性函数：

1、莫比乌斯函数

![20200722142652889.png][]

质因子个数为k

*μ*(*n*)的首25个值：1, −1, −1, 0, −1, 1, −1, 0, 0, 1, −1, 0, −1, 1, 1, 0, −1, 0, −1, 0, 1, 1, −1, 0, 0,

2.![2020072214302438.png][]欧拉函数 （比n小的与n互质的数的个数）

3.d(n) ~n的因子的个数（约数=因子）

4.![20200722143337614.png][]~约数和函数

还有一些常用的完全积性函数

1.e(n) 当n为1时值为1 其余情况为0

2.I(n) 恒为1

3.id(n) =n

狄利克雷卷积：

![20200722165323929.png][]![20200722165338439.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blcm1pX3lheGlsZW5p_size_16_color_FFFFFF_t_70][]

一些常用的狄利克雷卷积：

*μ*(*n*)\*I=e

*μ*(*n*)和I互为逆元函数

![20200723083702164.png][]

明显有![20200723083740325.png][]

id=n/d 所以可以得到该式子

![20200723083838786.png][]

![20200723083907994.png][]

最后一个也不难推，写出卷积易得。

以上结论都会在杜教筛时使用，或由其推导出需要的式子

还有一个结论：一个数n的所有约数的欧拉函数返回值的和为n

![20200723084136504.png][]

![watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blcm1pX3lheGlsZW5p_size_16_color_FFFFFF_t_70 1][]

数学公式不会打 好烦啊

[https_blog.csdn.net_beautiful_CXW_article_details_83143756]: https://blog.csdn.net/beautiful_CXW/article/details/83143756
[20200722164838232.png]: /images/20230209/6bb956d561be4ac58b0d401372fd1ffb.png
[70]: /images/20230209/9b930f2f8d244bd591e66c063c577bae.png
[20200722142652889.png]: /images/20230209/57343695b29c47039cce61af1e5826ed.png
[2020072214302438.png]: /images/20230209/cddb7426f493467392d480b565972872.png
[20200722143337614.png]: /images/20230209/80690d26e05b44e9a4a431fab73593c3.png
[20200722165323929.png]: https://img-blog.csdnimg.cn/20200722165323929.png
[20200722165338439.png]: /images/20230209/4986ec0d5c2b4979b55e8594132dcc79.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blcm1pX3lheGlsZW5p_size_16_color_FFFFFF_t_70]: /images/20230209/f07c97a3fa70465e958f5e956c5643cf.png
[20200723083702164.png]: /images/20230209/7e1845537bae4f8fa1792294e3043b59.png
[20200723083740325.png]: /images/20230209/7f191aed564d4ada92b778cb312c2fdf.png
[20200723083838786.png]: /images/20230209/886956f09f574b15acfcf9a0fe59ec70.png
[20200723083907994.png]: /images/20230209/b6486d1330a94bf7a066b75440ae4fbd.png
[20200723084136504.png]: /images/20230209/5280df61a4314174b129375bdada6aad.png
[watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG9nLmNzZG4ubmV0L3Blcm1pX3lheGlsZW5p_size_16_color_FFFFFF_t_70 1]: /images/20230209/83b5617198554e2e8506345fb833ab7d.png