数论基础

关键词

积性函数、狄利克雷卷积、莫比乌斯反演

先说几句

因为在此之前车璐典的课件已经写得很好了,我觉得我不可能写的比他更好。
所以我决定对于概念性的东西我尽量略过,仅仅当做自己的总结,而将大部分墨水放在一些比较新的题目上面。

积性函数

积性函数:在数论中,积性函数是指一个定义域为正整数n的算术函数f(n)有如下性质:f(1)=1且当a和b互质时f(ab)=f(a)f(b)。

完全积性函数:若一个函数f(n)有如下性质:f(1)=1且对两个随意正整数a和b而言f(ab)=f(a)f(b),则称此函数为完全积性函数。

几个积性函数的例子
φ(n)-欧拉函数,计算与n互质的正整数之数目
μ(n)-莫比乌斯函数,关于非平方数的质因子数目
d(n)-n的正因子数目
σ(n)-n的所有正因子之和
ε(n)-定义为:若n = 1,ε(n)=1;若 n > 1,ε(n)=0
1(n)-不变的函数,定义为1(n)=1(完全积性)
Id(n)-单位函数,定义为 Id(n)=n(完全积性)

狄利克雷卷积

对于函数f和g,定义其狄利克雷卷积为:

一些性质

一些例子

莫比乌斯反演

线性筛积性函数

我们先筛出每个数最小的质因子。

筛最小素数
for ( int i=1 ; i< SIZE ; i++ ) {
      if ( minp[i]==0 ) p[++cnt] = i ; // 筛出i以内的素数
      for ( int j=1 ; j<=cnt ; j++ ) {
            if ( i*p[j] >= SIZE ) break ; // 判断越界情况
            minp[ i*p[j] ] = p[j] ;
            if ( i%p[j] == 0 ) break ; 
      }
}

由于积性函数的性质,我们可以利用以前求过的函数值来求当前值。
例如:

POI2007 Zap

题目大意
Q个询问:每个询问三个数n、m、d,输出:

数据范围
n,m,Q,d<=50000

算法
解决这种问题一般是利用卷积简化公式,再用分块处理。

回顾上面所学到的:

剩下的就是考验基本功了。
莫比乌斯函数可以预处理出来。

假设n<=m
对于的情况,直接枚举。

对于的情况,都是不大于的。

所以直接枚举

对于当且仅当

所以求出边界,维护莫比乌斯函数的前缀和即可。

时间复杂度:

SDOI2014 数表

题目大意
Q个询问,每个询问三个数n,m,a,输出:

数据范围
Q<=20000
n,m<=100000
a<=1000000000

算法
(先不考虑a)

考虑到σ是可以线性筛出的,所以答案可以表示成:

卷积一下:

再简化:

然而到这一步我们依然不能解决问题。
我们令Q=dk:

也就是将他们卷积。
注意了,由于是积性函数,G也可以线性筛出来。
那么答案就可表示成:

如果没有a的约束的话,剩下的就是分块了。

但我们还差最后一步。
如果考虑a的约束,那么:

我们发现,如果不满足σ(k)<=a
那么他将对G(k),G(2k),G(3k)……的贡献为0。
换句话来说,如果满足σ(k)<=a
那么他将对G(k),G(2k),G(3k)……贡献μ(1)σ(k),μ(2)σ(k),μ(3)σ(k)……

那我们将询问按a值离线排序,同时将σ从小到大排序。
满足σ(k)<=a时更新G函数,最多次更新。

时间复杂度:

comments powered by Disqus