# [HDU4746] Mophues （莫比乌斯反演，数论分块）

### Description

As we know, any positive integer C ( C >= 2 ) can be written as the multiply of some prime numbers:
$C = p_1*p_2*p_3*...*p_k$
which $p_1, p_2 ... p_k$are all prime numbers.For example, if $C = 24$, then:
$24 = 2*2*2*3$
here, $p_1 = p_2 = p_3 = 2, p_4 = 3, k = 4$

Given two integers P and C. if k<=P( k is the number of C's prime factors), we call C a lucky number of P.

Now, XXX needs to count the number of pairs (a, b), which 1<=a<=n , 1<=b<=m, and gcd(a,b) is a lucky number of a given P ( "gcd" means "greatest common divisor").

Please note that we define 1 as lucky number of any non-negative integers because 1 has no prime factor.

HDU

## 解决思路

$\begin{cases} Fact(p)=1 \\ Fact(p^k)=k \\ Fact(p*i)=Fact(i)+1 \end{cases}$

$f(1)=\mu(\frac{1}{1})*g(1)+\mu(\frac{2}{1})*g(2)+\mu(\frac{3}{1})*g(3)...... \\ f(2)=\mu(\frac{2}{2})*g(2)+\mu(\frac{4}{2})*g(4)+\mu(\frac{6}{2})*g(6)...... \\ f(3)=\mu(\frac{3}{3})*g(3)+\mu(\frac{6}{3})*g(6)+\mu(\frac{9}{3})*g(9)...... \\ ...... \\ f(x)=\mu(\frac{1*x}{x})*g(1*x)+\mu(\frac{2*x}{x})*g(2*x)+\mu(\frac{3*x}{x})*g(3*x)......\\ =\mu(1)*g(1*x)+\mu(2)*g(2*x)+\mu(3)*g(3*x).....$

HNCJ OIer