积性函数的定义:如果算数函数f对于任意两个素数p,q均有f(pq)=f(p)f(q),那么称算数函数f为积性函数
在狄利克雷卷积中较常见的几种函数:
1.单位函数 id(n)=n
2.幂函数 Ik(n)=nk
3.元函数 ε(n)=(n==1?1:0)
4.因数和函数 σ(n)=sum(d)(n/d)
5.约数个数 d(n)=sum(1)(n/d)
在此附上模板代码
#include<bits/stdc++.h> #define ll long long using namespace std; int id(int n){ return n; } int Ik(int n,int k){ return (int)(pow(n,k)); } int e(int n){ return (n==1?1:0); } int S(int n){ int ans=0; for(int i=1;i*i<=n;i++){ if(n%i==0){ ans+=i; if(n/i!=i)ans+=n/i; } } return ans; } int d(int n){ int ans=0; for(int i=1;i*i<=n;i++){ if(n%i==0){ ans++; if(n/i!=i)ans++; } } return ans; } int main(){ return 0; }
积性函数比较常见的应用是狄利克雷卷积,莫比乌斯函数与反演,杜教筛等
标签:return,函数,积性,sum,int,id From: https://www.cnblogs.com/zhanghx-blogs/p/17533238.html