Problem Background

The math teacher assigned two Easy Math Problems to A.

Problem Description

Given \( n, c, f, l, r \), there are sets \( S = \{ x \in \mathbb{N}_+ \mid \gcd(x, n) \leq c \} \) and \( Q = \{ x \in S \mid l \leq x \leq r \} \).

• Set \( S \) includes all positive integers whose greatest common divisor with \( n \) is no more than \( c \). Set \( Q \) includes numbers from \( S \) that are not less than \( l \) and not greater than \( r \).

First question: Find the \( f \)-th smallest number in set \( S \).

Second question: Find the number of elements in set \( Q \).

Since the numbers are very large, A would like you to help him find the answers to these questions.

Input Format

A single line containing five integers \( n, c, f, l, r \) — as described in the problem statement.

Output Format

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

Sample Input and Output

Sample Input #1

12 3 8 10 17

Sample Output #1

11
6

Sample Input #2

72 5 66 13 89

Sample Output #2

94
54

Sample Input #3

360360 123 20200202 123456789 987654321

Sample Output #3

21751721
802555475

Notes

Sample 1 Explanation

\( S = \{1, 2, 3, 5, 7, 9, 10, 11, 13, 14, 15, 17, \dots\}, Q = \{10, 11, 13, 14, 15, 17\} \). The 8th smallest number in set \( S \) is 11, and the number of elements in set \( Q \) is 6.

Data Range and Constraints

This problem uses subtask testing.

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 data, \( 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

Thinking of solving this problem with \( n \log n \)?

Time Limits

For the first three subtasks, the time limit is 1 second. For the remaining subtask, the time limit is 500 milliseconds.

Source

Sweet Round 04 B

Idea & std: Alex_Wei, tester: xtx1092515503 & FrenkiedeJong21 & chenxia25

见题面 Input 部分

见题面 Output 部分