ODDDIV - Odd Numbers of Divisors
Given a positive odd integer K and two positive integers low and high, determine how many integers between low and high contain exactly K divisors.
Input
The first line of the input contains a positive integer C (0 < C < 100,000), the number of test cases to follow. Each case consists of a line containing three integers: K, low, and high (1 < K < 10000, 0 < low ≤ high < 10^10). K will always be an odd integer.
Output
Output for each case consists of one line: the number of integers between low and high, inclusive, that contain exactly K divisors.
Example
Input: 3 3 2 49 9 1 100 5 55 235 Output: 4 2 1
hide comments
smso:
2022-12-20 08:38:04
There are only 101 different divisors values: 1,3,5,...,1215,1323. I used smallest prime factors to speed up factorization.
|
|
kabbo25:
2020-05-02 13:25:43
prime_factorization+upper_bound+lower_bound
|
|
zakir068:
2020-03-14 06:16:05
Just one observation did the trick |
|
tarungupta:
2019-05-11 08:30:15
Must do problem! For help you can refer my repository "Spoj-Solutions" on github.com/12tarun |
|
nuhash_40:
2018-04-21 04:36:30
if wa try this
|
|
sy_117:
2018-04-06 16:07:05
Finally removed from TODO list after 2 yr 3 months :) Last edit: 2018-04-06 16:07:22 |
|
karthik1997:
2018-01-05 13:34:03
Pre Computation is the key for optimisation . AC 0.01s
|
|
aman224:
2017-03-03 11:10:57
Awesome problem...
|
|
rohith_rax:
2017-02-06 23:01:03
its says time limit exceeded . any hint pls ..
|
|
visvats_141095:
2016-06-23 00:46:39
perfect use of STLs ! :D
|
Added by: | eleusive |
Date: | 2008-10-04 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ERL JS-RHINO NODEJS PERL6 VB.NET |
Resource: | Al-Khawarizm 2008 - Set by eleusive |