#L. 集合

    Type: Default 1000ms 256MiB

集合

You cannot submit for this problem because the contest is ended. You can click "Open in Problem Set" to view this problem in normal mode.

Description

Caima 给你了所有 [a,b] 范围内的整数。一开始每个整数都属于各自的集合。每次你需要选择两个属于不同集合的整数,如果这两个整数拥有大于等于 pp 的公共质因数,那么把它们所在的集合合并。

重复如上操作,直到没有可以合并的集合为止。

现在 Caima 想知道,最后有多少个集合。

Format

Input

一行,共三个整数 a,b,p,用空格隔开。

Output

一个数,表示最终集合的个数。

Samples

10 20 3
7

Hint

样例 1 解释

对于样例给定的数据,最后有 {10,20,12,15,18},{13},{14},{16},{17},{19},{11}{10,20,12,15,18},{13},{14},{16},{17},{19},{11} 共 77 个集合,所以输出应该为 77。

数据规模与约定

对于 80% 的数据,1 ≤ a ≤ b ≤ 10^3 。 对于 100% 的数据,1 ≤ a ≤ b ≤ 10^5, 2 ≤ p ≤ b。

Limitation

1s, 1024KiB for each test case.

第七届SWPU-ACM老生预选赛

Not Attended
Status
Done
Rule
ACM/ICPC
Problem
187
Start at
2022-9-19 14:00
End at
2022-10-28 14:00
Duration
936 hour(s)
Host
Partic.
45