DMOPC '14 Contest 3 P4 - Not Enough Testers!

View as PDF
Submit solution
Points: 10 (partial)
Time limit: 1.0s
Memory limit: 256M
Author:
FatalEagle
Problem type

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 K, A, and B. How many numbers between A and B, inclusive, have exactly K factors?

To refresh your memory, a factor q of a number p is a number such that (1 \le q \le p) and the remainder of the division \dfrac{p}{q} is 0.

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 T times.

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 (%) T A,B K
1 5 T=1 1 \le A \le B \le 1\,000 1 \le K \le 2
2 5 T=1 1 \le A \le B \le 1\,000 1 \le K \le 3
3 5 T=1 1 \le A \le B \le 10\,000 1 \le K \le 2
4 5 T=1 1 \le A \le B \le 10\,000 1 \le K \le 3
5 5 T=1 1 \le A \le B \le 100\,000 1 \le K \le 2
6 5 T=1 1 \le A \le B \le 100\,000 1 \le K \le 3
7 5 1 \le T \le 1\,000 1 \le A \le B \le 1\,000 1 \le K \le 2
8 5 1 \le T \le 1\,000 1 \le A \le B \le 1\,000 1 \le K \le 3
9 5 1 \le T \le 10\,000 1 \le A \le B \le 10\,000 1 \le K \le 2
10 5 1 \le T \le 10\,000 1 \le A \le B \le 10\,000 1 \le K \le 3
11 5 1 \le T \le 100\,000 1 \le A \le B \le 100\,000 1 \le K \le 2
12 5 1 \le T \le 100\,000 1 \le A \le B \le 100\,000 1 \le K \le 3
13 10 1 \le T \le 1\,000 1 \le A \le B \le 1\,000 1 \le K \le 1\,000
14 10 1 \le T \le 10\,000 1 \le A \le B \le 10\,000 1 \le K \le 10\,000
15 20 1 \le T \le 100\,000 1 \le A \le B \le 100\,000 1 \le K \le 100\,000

Input Specification

The first line of input will have T, the number of instances of the problem you need to solve.

Each of the next T lines will contain three integers each separated from one another by a single space, K, A, and B.

Output Specification

There should be T lines of output. Each line should be a single integer, the answer to the problem with the given input.

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 1 factor is 1.

For the second case, the numbers that have 2 factors are 2, 3, 5, 7, 11, 13, 17, 19, 23, and 29.

For the third case, the numbers that have 3 factors are 4, 9, and 25.

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


  • 1
    P234rex  commented on Feb. 5, 2017, 2:57 a.m.

    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.


    • 3
      Paradox  commented on Feb. 5, 2017, 9:29 a.m.

      Precompute to handle queries in constant time.