#P2045. 双亲数

    ID: 1068 传统题 1000ms 256MiB 尝试: 1043 已通过: 371 难度: 6 上传者: 标签>CF1900普及+/提高-莫比乌斯反演交换求和顺序线性筛一维前缀和整除分块

双亲数

双亲数

题目描述

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

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

与正常双亲不太相同的是,对于同一个 dd,他的双亲太多了。

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

于是一个这样的问题摆在眼前,对于 1≤a≤A1 \leq a \leq A,1≤b≤B1 \leq b \leq B,有多少有序数对 (a,b)(a, b) 是 dd 的双亲数?

输入格式

输入只有一行三个整数,分别表示 A,B,dA, B, d。

输出格式

输出一行一个整数表示答案。

样例 #1

样例输入 #1

5 5 2

样例输出 #1

3

提示

样例 1 解释

共有三对双亲数:(2,2)(2, 2),(2,4)(2, 4),(4,2)(4, 2)。

数据规模与约定

  • 对于 40%40\% 的数据,保证 1≤A,B≤1061 \leq A, B \leq 10^6。
  • 对于 100%100\% 的数据,保证 1≤A,B≤1061 \leq A, B \leq 10^6,1≤d≤min⁡(A,B)1 \leq d \leq \min(A, B)。