#C. 【基础】集合

    Type: Default 1000ms 128MiB

【基础】集合

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.

说明

现在给你一些连续的整数,它们是从A到B的整数。一开始每个整数都属于各自的集合,然后你需要进行一下的操作:
每次选择两个属于不同集合的整数,如果这两个整数拥有大于等于P的公共质因数,那么把它们所在的集合合并。
反复如上操作,直到没有可以合并的集合为止。
现在请编程计算,最后有多少个集合。

输入格式

一行,三个整数A,B,P。

A≤B≤100000;
2≤P≤B。

输出格式

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

样例

10 20 3
7

提示

样例说明:7个符合条件的集合如下{10,20,12,15,18},{13},{14},{16},{17},{19},{11}。

第七届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