NFACTOR - N-Factorful
A number is called n-factorful if it has exactly n distinct prime factors. Given positive integers a, b, and n, your task is to find the number of integers between a and b, inclusive, that are n-factorful. We consider 1 to be 0-factorful.
Input
Your input will consist of a single integer T followed by a newline and T test cases. Each test case consists of a single line containing integers a, b, and n as described above.
T > 10000
1 ≤ a ≤ b ≤ 106
0 ≤ n ≤ 10
Output
Output for each test case one line containing the number of n-factorful integers in [a, b].
Example
Input: 5 1 3 1 1 10 2 1 10 3 1 100 3 1 1000 0 Output: 2 2 0 8 1
hide comments
divyansh96:
2024-04-03 12:27:12
Nice Question, Got it After some optimization :) |
|
joe201610a:
2022-04-06 21:49:02
BROOOO SO EASY AC IN ONE GO WITH FORMULA ONLY EZZZZZZZZZZZZ |
|
ramizouari:
2021-12-20 21:56:09
It can be solved using a Segment Tree, or even an Ordered Statistic Tree |
|
erne1309:
2021-07-22 03:55:29
got ac with sieve+prefix[10][1e6] |
|
conganon:
2021-07-05 04:12:26
:V
|
|
papan_97:
2020-10-16 16:19:33
How are people using upper/lower bound and why? I got ac in 0.40 seconds with simple sieve+prefix sum in cpp O_o |
|
fetus:
2020-06-27 09:50:52
NT:Be careful...
|
|
zhalok:
2020-05-23 09:35:38
how to do this using upper bound and lower bound
|
|
sahajjaiswal:
2020-05-15 13:58:54
The only thing I hate about spot discussions is "AC in one go". I really don't know why it's required here. I think that discussion platform is meant for doubts and clarification. |
|
amanjaiswal123:
2020-03-28 10:25:37
sd |
Added by: | periclesmachado |
Date: | 2011-01-30 |
Time limit: | 1.879s-2.484s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | Facebook Hacker Cup 2011 Round 1C |