双亲数

成绩 0 开启时间 2013年02月21日 星期四 23:02
折扣 0.8 折扣时间 2013年02月28日 星期四 23:02
允许迟交 是 关闭时间 2013年02月28日 星期四 23:02
输入文件 parents.in 输出文件 parents.out

【问题描述】

小 D 是一名数学爱好者，他对数字的着迷到了疯狂的程度。

我们以 d = gcd(a, b) 表示 a 、 b 的最大公约数，小 D 执著的认为，这样亲密的关系足可以用双亲来描述，此时，我们称 有序 数对 (a, b) 为 d 的双亲数。

与正常双亲不太相同的是，对于同一个 d ，他的双亲太多了 >_<

比如， (4, 6), (6, 4), (2, 100) 都是 2 的双亲数。

于是一个这样的问题摆在眼前，对于 0 < a <= A, 0 < b <= B ，有多少 有序 数对 (a, b) 是 d 的双亲数？

 

【输入文件】

输入文件只有一行，三个正整数 A 、 B 、 d (d <= A, B) ，意义如题所示。

 

【输出文件】

输出一行一个整数，给出满足条件的双亲数的个数。

 

【数据约定】

对于 40% 的数据满足 0 < A, B < 10^4

对于 100% 的数据满足 0 < A, B < 10^6

 

【样例】

输入样例

5 5 2

输出样例

3

【样例解释】

满足条件的三对双亲数为 (2, 2) (2, 4) (4, 2)