[toggle hide="yes" title="题目" color=""]

Description

给出N,M,K,求
$$\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k mod 1000000007$$

Input

输入有多组数据,输入数据的第一行两个正整数T,K,代表有T组数据,K的意义如上所示,下面第二行到第T+1行,每行为两个正整数N,M,其意义如上式所示。

Output

如题

Sample Input

1 2
3 3

Sample Output

20

HINT

1<=N,M,K<=5000000,1<=T<=2000

[/toggle]

反演好题,关于推式子的部分,有个很好的题解,直接粘上来:

$$\begin{eqnarray*} &&\sum_{i=1}^n\sum_{j=1}^m\gcd(i,j)^k\\ &=&\sum_d d^k\sum_{i=1}^n\sum_{j=1}^m[\gcd(i,j)=d]\\ &=&\sum_d d^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}[\gcd(i,j)=1]\\ &=&\sum_d d^k\sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{m}{d}\rfloor}\sum_{u|i,u|j}\mu(u)\\ &=&\sum_d d^k\sum_{u}\mu(u)\lfloor\frac{n}{du}\rfloor\lfloor\frac{m}{du}\rfloor\\ &=&\sum_D \lfloor\frac{n}{D}\rfloor\lfloor\frac{m}{D}\rfloor\sum_{d|D}d^k\mu(\frac{D}{d})\\ &=&\sum_D \lfloor\frac{n}{D}\rfloor\lfloor\frac{m}{D}\rfloor F(D) \end{eqnarray*}$$

这样,可以发现F(x)即为积性函数的狄利克雷卷积,即F也是积性函数,可以线性筛。

分情况考虑线性筛的三种情况:

1.当x为素数时,显然有:$$F(x)=x^{k}-1$$

2.当prime[j]与枚举的i互质时,根据积性函数的性质,有:$$F(i*prime[j])=F(i)*F(prime[j])$$

3.当prime[j]与枚举的i不互质时,考虑新加入的因子对枚举造成的贡献。若枚举到的d不含因子prime[j],则其mu值一定为0,对答案无贡献,其余情况将每个位置的d带入乘上prime[j],可得,有 $$F(i*prime[j])= F(i) * prime[j] ^{k} $$ .

感谢渊哥耐心教导!!!

 


Narcissus | HZOIer | zhuohaoyu1228@gmail.com | QQ 943382974