P6210 "SWTR-4" Easy Math Problems

The math teacher assigned Little A $2$ Easy Math Problems.

Given $n,c,f,l,r$, define the set $S=\{x\in\mathbb{N_+}\mid\gcd(x,n)\leq c\}$ and the set $Q=\{x\in S\mid l\leq x\leq r\}$. - Set $S$ contains all positive integers whose $\gcd$ with $n$ is at most $c$, and set $Q$ contains the elements in $S$ that are not less than $l$ and not greater than $r$. Question 1: Find the $f$-th smallest number in set $S$. Question 2: Find the number of elements in set $Q$. Since the numbers are very large, Little A wants you to help compute the answers.

A single line with five integers $n,c,f,l,r$ — with meanings as described in the statement.

Output two lines of integers — the first line is the answer to Question 1, and the second line is the answer to Question 2.

[Sample $1$ Explanation] $S=\{1,2,3,5,7,9,10,11,13,14,15,17,\dots\},Q=\{10,11,13,14,15,17\}$. It can be seen that the $8$-th smallest number in $S$ is $11$, and the number of elements in $Q$ is $6$. [Constraints and Notes] **This problem uses bundled tests.** Subtask $1(15\%)$: $n\leq 10^3$, $r\leq 10^3$, $f\leq 10^3$. Subtask $2(35\%)$: $n\leq 10^5$, $r\leq 10^5$, $f\leq 10^5$. Subtask $3(35\%)$: $n\leq 10^6$, $r\leq 10^{12}$, $f\leq 10^{12}$. Subtask $4(15\%)$: $n\leq 10^7$, $r\leq 10^{10^5}$, $f\leq 10^{10^5}$. For $100\%$ of the testdata, $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] Want to solve this problem with $n\log n$? [Time Limit] For the first $3$ subtasks, the time limit is $1\rm{s}$, and for the remaining subtask it is $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), verification: [xtx1092515503](https://www.luogu.com.cn/user/123369) & [FrenkiedeJong21](https://www.luogu.com.cn/user/203968) & [chenxia25](https://www.luogu.com.cn/user/138400) Translated by ChatGPT 5