TGCD2 - Trending GCD (Hard)
This problem is a harder version of TRENDGCD.
Given $n$ and $m$, compute
$$ S(n, m) = \sum_{i=1}^n \sum_{j=1}^m ij \cdot f(\gcd(i,j)), $$
where $f(n) = (\mu(n))^2 n$ and $\mu(n)$ is the Möbius function, that is, $f(n) = n$ if $n$ is square-free and $0$ otherwise. Especially, $f(1)=1$.
Input
The first line contains an integer $T$, indicating the number of test cases.
Each of the next $T$ lines contains two positive integers $n$ and $m$.
Output
For each test case, print $S(n, m)$ modulo $10^9+7$ in a single line.
Example
Input: 5
42 18
35 1
20 25
123456789 987654321
233333333333 233333333333 Output: 306395
630
128819
897063534
355737203
Constraints
There are 6 test files.
Test #0: $1 \leq T \leq 10000$, $1 \leq n, m \leq 10^7$.
Test #1: $1 \leq T \leq 200$, $1 \leq n, m \leq 10^8$.
Test #2: $1 \leq T \leq 40$, $1 \leq n, m \leq 10^9$.
Test #3: $1 \leq T \leq 10$, $1 \leq n, m \leq 10^{10}$.
Test #4: $1 \leq T \leq 2$, $1 \leq n, m \leq 10^{11}$.
Test #5: $T = 1$, $1 \leq n, m \leq 235711131719$.
@Speed Addicts: My solution runs in 20.76s (total time). (approx 3.46s per file)
WARNING: The time limit may be somewhat strict.
Added by: | liouzhou_101 |
Date: | 2019-03-27 |
Time limit: | 20s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | TRENDGCD |