|
||||||||||
Yet Another Easy Function Sum ProblemTime Limit: 40000/20000 MS (Java/Others) Memory Limit: 524288/524288 K (Java/Others)Total Submission(s): 70 Accepted Submission(s): 11 Problem Description Two years ago, Silver187 learned Mobius inversion and knew how to calculate ($1\le n\le 10^9$) $$ \sum_{i=1}^n \sum_{j=1}^n \gcd(i,j) $$ One year ago, Silver187 learned how to calculate ($1\le n\le 10^5$) $$ \sum_{i=1}^n \sum_{j=1}^n \varphi(ij) $$ But he tried to solve this problem when $1\le n\le 10^9$. Finally, he failed to solve it. But he didn't completely fail, he solved a similar problem: Silver187 defines that if $n=\prod_{i=1}^k p_i^{\alpha_i}(p_i\in \operatorname{prime} ,\alpha_i\gt0, \forall i \ne j, p_i \ne p_j)$ , then $H(n)=\prod_{i= 1}^k p_i$. In particular, $H(1)=1$. Silver187 likes gcd, so he wants to ask you to calculate the result of the following formula. $$ (\sum_{i=1}^n \sum_{j=1}^n H(ij)[\gcd(i,j)=1])\bmod 10^9+7 $$ Now, Silver187 asks you to solve this problem. Input First line has one integer $T(1≤T≤5)$, indicating there are $T$ test cases. In each case: Only one line contains an integer $n(1\le n\le 10^9)$. Input guarantee $\sum n\le 2\times 10^9$. Output In each case, output an integer on a line. Sample Input
Sample Output
Source | ||||||||||
|