[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

题目大意

Fact(x)表示把x唯一分解后，分解出来的质因子的个数（注意，相同的质因子不算同一个），求$\sum_{i}^{n} \sum_{j}^{m} [Fact(gcd(i,j))<=P]$

解决思路

p为质数
$\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 一枚