[原创]SPOJ PGCD - Primes in GCD Table [莫比乌斯反演＋分段+求和优化]【组合数学】

2017-02-14 21:02:29 Tabris_ 阅读数：619

https://blog.csdn.net/qq_33184171/article/details/55106268

--------------------------------------------------------------------------------------------.
PGCD - Primes in GCD Table

Johnny has created a table which encodes the results of some operation – a function of two arguments. But instead of a boring multiplication table of the sort you learn by heart at prep-school, he has created a GCD (greatest common divisor) table! So he now has a table (of height a and width b), indexed from (1,1) to (a,b), and with the value of field (i,j) equal to gcd(i,j). He wants to know how many times he has used prime numbers when writing the table.

Input

First, t ≤ 10, the number of test cases. Each test case consists of two integers, 1 ≤ a,b < 10^7.

Output

For each test case write one number - the number of prime numbers Johnny wrote in that test case.

Example

Input:
2
10 10
100 100

Output:
30
2791

--------------------------------------------------------------------------------------------.

$f(d) = \sum_{x=1}^{n} \sum_{y=1}^{m} \big [\gcd(x,y)=p \big]$ (其中P为素数,[] 括号内式子成立为1,否则0)
$F(d)=\sum_{x=1}^{n} \sum_{y=1}^{m} \big [d|\gcd(x,y)]\\同时 F(d) = \big[\dfrac{n}{d}\big]\big[\dfrac{m}{d}\big]$

$f(d) = \sum _{d|n}\mu(\frac{n}{d})F(d)$ (1)
$f(n) = \sum _{d|n}\mu(d)F(\frac{n}{d})$ (2)

$f(d) = \sum_{d|n}\mu(\frac{n}{d})\big[\dfrac{n}{d}\big]\big[\dfrac{m}{d}\big]$ (1)

$ans = \sum_{p}^{min(n,m)}f(p) \\ =\sum_{p}^{min(n,m)}\sum_{d=1}^{min(n,m)/p}\mu({d})\big[\dfrac{n/p}{d}\big]\big[\dfrac{m/p}{d}\big]$

$\sum_{p}^{min(n,m)} \sum_{d=1}^{min(n,m)/p}\mu({d})\big[\dfrac{n}{t}\big]\big[\dfrac{m}{t}\big]\\=\sum_{t=1}^{min(n,m)} \sum_{p \big| p<=n,p|t,p为素数} \mu(\frac{t}{p})\big[\dfrac{n}{t}\big]\big[\dfrac{m}{t}\big]$

--------------------------------------------------------------------------------------------.