NGIRL - Namit In Trouble
Namit's girlfriend's birthday is coming next week. He went to a gift shop and saw N gifts are arranged in a single row in such a way that the position at which the gift is placed is equal to its price. (Position starts from 1.)
Namit's girlfriend being a maths student like those numbers which have exactly 3 divisors, so Namit decide to buy only those gifts which are placed at a position which have only 3 divisors, but Namit's girlfriend likes gifts whose price are above a certain amountK.
Now Namit wants to know total choices he have and how many gifts his girlfriend like for a given value of N.
Input
Input starts with 1<=T<=1000 (number of test cases). Then T lines follows each containing two integer 1<=N<10^10 (number of gifts at gift shop) and 1<=K<=10^10.
Output
You program should output two values indicating total number of choices and the number of gifts Namit's girlfriend likes.
Example
Input: 3 10 2 20 7 10 4 Output: 2 2 2 1 2 1
hide comments
|
ayush_chavan:
2024-03-30 10:43:11
those who r confuse why to use sieve , we have to sieve becoz , the numbers which have exactly 3 divisors are the square of prime numbers , and dont create an array of size 10^10 for sieve we need squares so create of size 100001 and use prefix sum for precomputing the values |
|
satish7978:
2024-02-26 13:39:43
sieve & prefix sum [O(1) in comparison to O(logN) in binary]. |
|
joe201810a:
2022-04-06 20:52:01
its easy without sieve or binary search
|
|
lumaks_69:
2022-02-07 11:54:44
k > n exists |
|
anchord:
2021-05-03 21:25:32
can someone explain me why to use sieve while the question asked you to find out the number of exactly 3 divisors? |
|
auler_:
2020-06-26 16:18:21
You do not need binary search. Simple sieve gave me AC |
|
amdee07:
2020-05-21 08:56:58
just take constraint 10^5 i.e. (10^5)^2<=10^10.
|
|
deependra_18:
2020-04-14 06:44:18
thanks @avasthiayush k>n cost me 3 WA . |
|
avasthiayush:
2020-04-02 13:07:50
Must consider the condition when k>n :) |
|
lx_lovin:
2020-01-08 18:25:38
Sieve Of Eratosthenes + Binary Search -> AC |
| Added by: | JUNK |
| Date: | 2017-03-06 |
| Time limit: | 0.100s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All |
| Resource: | Own Problem |
RSS