# [HDU1695]GCD （莫比乌斯反演）

### Description

Given 5 integers: a, b, c, d, k, you're to find x in a...b, y in c...d that GCD(x, y) = k. GCD(x, y) means the greatest common divisor of x and y. Since the number of choices may be very large, you're only required to output the total number of different number pairs.
Please notice that, (x=5, y=7) and (x=7, y=5) are considered to be the same.

Yoiu can assume that a = c = 1 in all test cases.

HDU

## 解决思路

$G(x)=\sum_{x|d} \sum_i^a \sum_j^b [gcd(i,j)==d]=\lfloor \frac{a}{x} \rfloor * \lfloor \frac{b}{x} \rfloor$

$F(x)=\sum_{x|d} \mu (\frac{d}{x}) * \lfloor \frac{a}{d} \rfloor * \lfloor \frac{b}{d} \rfloor$

HNCJ OIer