PGCD2 - Primes in GCD Table (Hard)
This problem is a harder version of PGCD.
Let $P$ be the set of all prime numbers. For two positive integers $n$ and $m$, define
$$ f(n,m) = \sum_{i=1}^n \sum_{j=1}^m [\gcd(i,j) \in P], $$
which counts the number of prime numbers among the greatest common divisors $\gcd(i,j)$ for $1 \leq i \leq n$ and $1 \leq j \leq m$.
Your task: given $n$ and $m$, compute $f(n,m)$.
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 $f(n, m)$ in a single line.
Example
Input: 4
10 10
100 100
123456789 987654321
233333333333 233333333333 Output: 30
2791
33523360713808196
14968599673221238693021
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 4.87s (total time). (approx 0.81s per file)
Added by: | liouzhou_101 |
Date: | 2019-03-22 |
Time limit: | 20s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |
Resource: | PGCD |