Amagi Brilliant Contests runs a business making and hosting contests on its online platform for competitive programmers who want to run their own contests.
Making a problem for a contest is a multi-step process. One of the steps involves having someone other than the problem writer independently solve the problem to make sure the author's test data and solution are correct.
One problem that has not yet been tested is as follows:
You are given three numbers
, , and . How many numbers between and , inclusive, have exactly factors? To refresh your memory, a factor
of a number is a number such that and the remainder of the division is .
For this particular problem, there are a lot of cases the problem writer wants to test. Therefore, the problem tester will have to solve the aforementioned problem
You are the head of the number theory department at Amagi Brilliant Contests, and so you have been tasked with testing out this problem.
Constraints
There will be a number of subtasks for this problem:
Test Case Batch | Points (%) | |||
---|---|---|---|---|
1 | 5 | |||
2 | 5 | |||
3 | 5 | |||
4 | 5 | |||
5 | 5 | |||
6 | 5 | |||
7 | 5 | |||
8 | 5 | |||
9 | 5 | |||
10 | 5 | |||
11 | 5 | |||
12 | 5 | |||
13 | 10 | |||
14 | 10 | |||
15 | 20 |
Input Specification
The first line of input will have
Each of the next
Output Specification
There should be
Sample Input
3
1 1 30
2 1 30
3 1 30
Sample Output
1
10
3
Explanation for Sample Output
For the first case, the only number that has
For the second case, the numbers that have
For the third case, the numbers that have
Hint
For users using the Python language, it is advised to use fast input/output methods such as those described on the tips page.
Comments
Any hints on how not to TLE? or at least hints on what i'm doing wrong? I'm pretty sure i did the fast input thing correctly.
Precompute to handle queries in constant time.