P6210 「SWTR-4」Easy Math Problems

数学老师给小 A 布置了 $2$ 道 Easy Math Problems。

给定 $n,c,f,l,r$，有集合 $S=\{x\in\mathbb{N_+}\mid\gcd(x,n)\leq c\}$ 和集合 $Q=\{x\in S\mid l\leq x\leq r\}$。 - 集合 $S$ 为所有与 $n$ 的 $\gcd$ 不超过 $c$ 的正整数，集合 $Q$ 为 $S$ 中不小于 $l$，不大于 $r$ 的数。 第一问：请求出集合 $S$ 中第 $f$ 小的数。 第二问：请求出集合 $Q$ 中包含的元素个数。 由于数字很大，所以小 A 想请你帮他求出问题的答案。

无

无

【样例 $1$ 说明】 $S=\{1,2,3,5,7,9,10,11,13,14,15,17,\dots\},Q=\{10,11,13,14,15,17\}$，可知集合 $S$ 第 $8$ 小的数为 $11$，集合 $Q$ 中包含的元素个数为 $6$。 【数据范围与约定】 **本题使用捆绑测试**。 子任务 $1(15\%)$：$n\leq 10^3$，$r\leq 10^3$，$f\leq 10^3$。 子任务 $2(35\%)$：$n\leq 10^5$，$r\leq 10^5$，$f\leq 10^5$。 子任务 $3(35\%)$：$n\leq 10^6$，$r\leq 10^{12}$，$f\leq 10^{12}$。 子任务 $4(15\%)$：$n\leq 10^7$，$r\leq 10^{10^5}$，$f\leq 10^{10^5}$。 对于 $100\%$ 的数据，$1\leq c\leq n\leq 10^7$，$1\leq l\leq r\leq 10^{10^5}$，$1\leq f\leq 10^{10^5}$。 【Tips】 想用 $n\log n$ 过这道题？ 【时间限制】 对于前 $3$ 个子任务，时间限制 $1\rm{s}$，剩下一个子任务 $500\rm{ms}$。 【Source】 [Sweet Round 04](https://www.luogu.com.cn/contest/26414)$\ \ $B idea & std：[Alex_Wei](https://www.luogu.com.cn/user/123294)，验题：[xtx1092515503](https://www.luogu.com.cn/user/123369) & [FrenkiedeJong21](https://www.luogu.com.cn/user/203968) & [chenxia25](https://www.luogu.com.cn/user/138400)