name
Easy Math Problem
descirption
One day, Touma Kazusa encountered a easy math problem. Given n and k, she need to calculate the following sum modulo $1e9+7$.
$$∑_{i=1}^n∑^n_{j=1}gcd(i,j)^klcm(i,j)[gcd(i,j)∈prime]%(1e9+7) $$
However, as a poor student, Kazusa obviously did not, so Touma Kazusa went to ask Kitahara Haruki. But Kitahara Haruki is too busy, in order to prove that he is a skilled man, so he threw this problem to you. Can you answer this easy math problem quickly?
input
There are multiple test cases.$（T=5）$ The first line of the input contains an integer$T$, indicating the number of test cases. For each test case:
There are only two positive integers n and k which are separated by spaces.
$1≤n≤1e10$
$1≤k≤100$
output
An integer representing your answer.
sample input
1
10 2
sample output
2829
toturial
$$
\begin{aligned}
&\sum_{i=1}^n\sum_{j=1}^n ijgcd(i,j)^{k-1} gcd is prime
\=&\sum_{d\in prime} \sum_{i=1}^n\sum_{j=1}^nijd^{k-1}[gcd(i,j)=d]
\=&\sum_{d\in prime} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ijd^{k+1}[gcd(i,j)=1]
\=&\sum_{d\in prime}d^{k+1} \sum_{i=1}^{\lfloor\frac{n}{d}\rfloor}\sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}ij[gcd(i,j)=1]
\=&\sum_{d\in prime}d^{k+1} \sum_{j=1}^{\lfloor\frac{n}{d}\rfloor}j^2\phi(j)
\end{aligned}
$$
我们可以对n分块了，前面可以min25筛
$\begin{aligned}f(j)=j^2\phi(j)\end{aligned}$
$\begin{aligned}g(j)=j^2\end{aligned}$
$\begin{aligned}f\ast g(j)=\sum_{i|j}i^2\phi(i)(\frac{j}{i})^2=j^2\sum_{i|j}\phi(i)=j^2(\phi\ast 1)(j)=j^3\end{aligned}$
于是后面可以杜教筛
code
1 |
|
- 本文作者： fightinggg
- 本文链接： http://fightinggg.github.io/yilia/yilia/Q056L8.html
- 版权声明： 本博客所有文章除特别声明外，均采用 MIT 许可协议。转载请注明出处！