题目背景

数学老师给小 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 想请你帮他求出问题的答案。

输入格式

一行五个整数 $n,c,f,l,r$ —— 意义见题目描述。

输出格式

输出两行整数 —— 第一行为第一问的答案，第二行为第二问的答案。

12 3 8 10 17

11
6

72 5 66 13 89

94
54

360360 123 20200202 123456789 987654321

21751721
802555475

提示

【样例 $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$\ \$B

idea & std：Alex_Wei，验题：xtx1092515503 & FrenkiedeJong21 & chenxia25