[HDU1695]GCD (莫比乌斯反演)

发布于 2018-01-13  35 次阅读


本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[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.

Http

HDU

Tag

莫比乌斯反演

题目大意

给定\(a,b,K\)求\(\sum_i^a \sum_j^b [gcd(i,j)==K]\)

解决思路

设\[F(x)=\sum_i^a \sum_j^b [gcd(i,j)==K]\] \[G(x)=\sum_{x|d} F(d)\]
\[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 \]
但是同时要注意到,题目中表明了(a,b)(b,a)是同一种方案,所以接下来考虑如何去重。
我们假定a\leq b,记包括了重复的答案为ans。我们知道[1,a]的方案是被重复算了的,所以我们再算一遍到a的代价,记为sum。需要注意的是,这里的sum中计算的也是计算了两次的,所以最终的答案应该是sum-\frac{ans}{2}
最后要注意的是,K可以取到0,所以要特判

代码

本文章由SYCstudio或本站其它作者所有,严禁转载,转载必究

本文链接地址:[HDU1695]GCD (莫比乌斯反演)


HNCJ OIer 一枚