积性函数、线性筛、莫比乌斯反演和一堆乱七八糟的题目 - jcvb

积性函数、线性筛、莫比乌斯反演和一堆乱七八糟的题目

jcvb posted @ 2013年12月03日 15:07 , 8884 阅读

联赛AK了真高欣(虽然题目都是大水比=-=)。联赛后到现在一直在做数论学了好多神奇的东西都记在这儿吧哈哈。

==============================================================================

·积性函数
定义在正整数集上的函数[tex]f(n)[/tex](称为算术函数),若[tex]\text g \text c \text d(a,b)=1[/tex]时有[tex]f(a)f(b)=f(ab)[/tex],则[tex]f(x)[/tex]称为积性函数。
一个显然的性质:(非恒等于零的)积性函数[tex]f(n)[/tex]必然满足[tex]f(1)=1[/tex]。
定义逐点加法[tex](f+g)(x)=f(x)+g(x),逐点乘法(f\cdot g)(x)=f(x)g(x)[/tex]。
一个比较显然的性质:若[tex]f,g[/tex]均为积性函数,则[tex]f\cdot g[/tex]也是积性函数。
积性函数的求值:[tex]n=\prod p_i^{\alpha_i}[/tex],则[tex]f(n)=\prod f(p_i^{\alpha_i})[/tex],所以只要解决[tex]n=p^\alpha[/tex]时[tex]f(n)[/tex]的值即可。

例如:
恒为1的常函数[tex]1(n)=1[/tex],
恒等函数[tex]\text{id}(n)=n[/tex], 
单位函数[tex]\epsilon(n)=[n==1][/tex],(这三个都是显然为积性)
欧拉函数[tex]\varphi(n)[/tex] (只要证两个集合相等就能证明积性)
莫比乌斯函数[tex]\mu(n)[/tex] (由定义也是显然的)

·Dirichlet卷积
对两个算术函数[tex]f,g[/tex],定义其Dirichlet卷积为新函数[tex]f*g[/tex],满足[tex](f*g)(n)=\sum_{d|n}{f(d)g(n/d)}[/tex]。
一些性质:
交换律[tex]f*g=g*f[/tex],
结合律[tex](f*g)*h=f*(g*h)[/tex],
单位元[tex]f*\epsilon=f[/tex],
对逐点加法的分配律[tex]f*(g+h)=f*g+f*h[/tex]

重要性质:若[tex]f,g[/tex]均为积性函数,则[tex]f*g[/tex]也是积性函数。(展开式子即可证明)
[tex]n[/tex]的约数个数[tex]d(n)[/tex]可以写成[tex]d(n)=(1*1)(n)[/tex];约数和[tex]\sigma(n)[/tex]可以写成[tex]\sigma(n)=(1*\text{id})(n)[/tex],由上面的性质可知这两个函数均是积性函数。

重要性质:[tex]\sum_{d|n}{\mu(d)}=[n==1][/tex],即[tex]1*\mu=\epsilon[/tex]。(可用二项式定理证明)
重要性质:[tex]\sum_{d|n}{\varphi(d)}=n[/tex],即[tex]1*\varphi=\text{id}[/tex]。(n是质数时显然成立,再由积性得证)

·O(nlgn)预处理Dirichlet卷积
若已知[tex]f(i),g(i),i=1,2,\dots,n[/tex]的值,则可以在O(nlgn)时间内计算出[tex](f*g)(i),i=1,2,\dots,n[/tex]。

int f[MAXN],g[MAXN],h[MAXN]={0};
void calc(int n)
{    
    for (int i=1;i*i<=n;i++)
        for (int j=i;i*j<=n;j++)
            if(j==i)h[i*j]+=f[i]*g[i];
            else h[i*j]+=f[i]*g[j]+f[j]*g[i];
}

·线性筛O(n)预处理

int pr[MAXN],bo[MAXN]={0},tot=0;
void sieve(int n){
	for (int i=2;i<=n;i++){
		if(!bo[i])pr[++tot]=i;
		for (int j=1;j<=tot && pr[j]*i<=n;j++){
			bo[i*pr[j]]=1;
			if(i%pr[j]==0)break;
		}
	}
}

可以证明每个合数只会被其最小质因子筛去,因此复杂度为线性。
如果能够充分挖掘[tex]f(n)[/tex]的性质,则可以用线性筛在O(n)时间内预处理[tex]f(i),i=1,2,\dots,n[/tex]。
关键在于对下面三种情况分别进行处理:
1.[tex]x[/tex]是质数,求[tex]f(x)[/tex]
2.[tex]p[/tex]是质数,[tex]p\nmid x[/tex],求[tex]f(px)[/tex]
3.[tex]p[/tex]是质数,[tex]p\mid x[/tex],求[tex]f(px)[/tex]
第1种情况往往比较简单。如果能证明[tex]f[/tex]是积性函数,则容易知道第2种情况是[tex]f(px)=f(p)f(x)[/tex],剩下只要解决第3种情况的递推就够了。
有时虽然[tex]f[/tex]不是积性函数,但也能够通过分析其性质分别解决这三种情况(后面会举一些例子)。

·一堆题目
以下均默认[tex]a\leq b[/tex]
1101: [POI2007]Zap
令[tex]a'=\left \lfloor a/d \right \rfloor,b'=\left \lfloor b/d \right \rfloor[/tex]
[tex]\sum_{i=1}^a\sum_{j=1}^b[\text{gcd}(i,j)==d][/tex]
[tex]=\sum_{i=1}^{a'}\sum_{j=1}^{b'}[\text{gcd}(i,j)==1][/tex]
用莫比乌斯函数的性质把求和的式子换掉,
[tex]=\sum_{i=1}^{a'}\sum_{j=1}^{b'}\sum_{d|\text{gcd}(i,j)}\mu(d)[/tex]
其中[tex]d|\text{gcd}(i,j) \Leftrightarrow d|i \,\text{and} \,d|j[/tex],更换求和指标,
[tex]=\sum_{d=1}^{a'}\mu(d)\left \lfloor a'/d \right \rfloor \left \lfloor b'/d \right \rfloor[/tex]
容易知道[tex]\left\lfloor a'/d\right \rfloor[/tex]单调不上升,且最多有[tex]2\sqrt{a'}[/tex]种不同的取值。所以按取值分成[tex]O(\sqrt{n})[/tex]个段分别处理,一个连续段内的和可以用预处理出的莫比乌斯函数前缀和求出。

if(a>b)swap(a,b);
int nex;
ll ans=0;
for (int i=1;i<=a;i=nex+1){
	nex=min(a/(a/i),b/(b/i));
	ans+=1ll*(s[nex]-s[i-1])*(a/i)*(b/i);
}

整道题目预处理O(n),每次询问O(sqrt(n))。

2005: [Noi2010]能量采集
[tex]\sum_{i=1}^a\sum_{j=1}^b\text{gcd}(i,j)[/tex]
[tex]=\sum_{d=1}^a \sum_{i=1}^{\left \lfloor a/d \right \rfloor}\sum_{j=1}^{\left \lfloor b/d \right \rfloor}d[\text{gcd}(i,j)==1][/tex]
套用上题,
[tex]=\sum_{d=1}^a \sum_{d'=1}^{\left \lfloor a/d \right \rfloor}d\mu(d')\left \lfloor a/dd' \right \rfloor \left \lfloor b/dd' \right \rfloor[/tex]
关键一步,作代换[tex]D=dd'[/tex],把求和指标d,d'改为D,d,(容易证明这是等价的)
[tex]=\sum_{D=1}^a \sum_{d|D}d\mu(D/d)\left \lfloor a/D\right \rfloor \left \lfloor b/D\right \rfloor[/tex]
[tex]=\sum_{D=1}^a \left \lfloor a/D\right \rfloor \left \lfloor b/D\right \rfloor (\text{id}*\mu)(D)[/tex]
由[tex]\varphi*1=\text{id}[/tex],有[tex]\text{id}*\mu=\varphi[/tex],
[tex]=\sum_{D=1}^a \left \lfloor a/D\right \rfloor \left \lfloor b/D\right \rfloor \varphi(D)[/tex]
最后处理方式同上题。(不过原题只有一个询问,不分段也不要紧)

2693: jzptab
[tex]\sum_{i=1}^a\sum_{j=1}^b ij/\text{gcd}(i,j)[/tex]
[tex]=\sum_{d=1}^a\sum_{i=1}^{\left \lfloor a/d\right \rfloor}\sum_{j=1}^{\left \lfloor b/d\right \rfloor}ijd[\text{gcd}(i,j)==1][/tex]
类似的方法将方括号换掉,化简为
[tex]=\sum_{d=1}^a\sum_{d'=1}^{\left \lfloor a/d\right \rfloor}\sum_{i=1}^{\left \lfloor a/dd' \right \rfloor}\sum_{j=1}^{\left \lfloor b/dd' \right \rfloor}d\mu(d')d'^2ij[/tex]
由等差数列求和,
[tex]=\sum_{d=1}^a\sum_{d'=1}^{\left \lfloor a/d \right \rfloor}d\mu(d')d'^2\text{sum}(\left \lfloor a/dd' \right \rfloor,\left \lfloor b/dd' \right \rfloor)[/tex]
其中[tex]\text{sum}(a,b)=a(a+1)b(b+1)/4[/tex],
像上题一样代换求和指标,
[tex]=\sum_{D=1}^a D \text{sum}(\left \lfloor a/D \right \rfloor,\left \lfloor b/D \right \rfloor)\sum_{d'|D}d'\mu(d')[/tex]
[tex]=\sum_{D=1}^a D\cdot((\text{id}\cdot \mu)*1)(D) \text{sum}(\left \lfloor a/D \right \rfloor,\left \lfloor b/D \right \rfloor)[/tex]
处理方式同上。
 

3309: DZY Loves Math
类似的方法化简得
[tex]\sum_{D=1}^a (\mu * f)(D) \left \lfloor a/D \right \rfloor \left \lfloor b/D \right \rfloor [/tex]
记[tex]g=\mu * f[/tex],[tex]g[/tex]并不是积性函数。
观察[tex]g(n)[/tex]的取值可以发现,
[tex]g(1)=0[/tex];
否则,当[tex]n=(\prod_{i=1}^k p_i)^\alpha=\prod_{i=1}^k p_i^\alpha[/tex]时,[tex]g(n)=(-1)^{k+1}[/tex];
否则,[tex]n[/tex]中存在两个质因子的次数不相同,[tex]g(n)=0[/tex]。
上述性质容易通过展开[tex]g(\prod p_i^{\alpha_i})[/tex]得到证明。
这样,在线性筛的同时记录[tex]n[/tex]的最小质因子[tex]p_1[/tex]的次数[tex]\alpha_1[/tex],以及[tex]\frac{n}{p_1^{\alpha_1}}[/tex]即可。
 

Host by is-Programmer.com | Power by Chito 1.3.3 beta | © 2007 LinuxGem | Design by Matthew "Agent Spork" McGee