Background

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

Problem Description

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.

Input Format

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

Output Format

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

12 3 8 10 17

11
6

72 5 66 13 89

94
54

360360 123 20200202 123456789 987654321

21751721
802555475

Hint

[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$\ \$B

idea & std: Alex_Wei, verification: xtx1092515503 & FrenkiedeJong21 & chenxia25

Translated by ChatGPT 5