联赛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]即可。