HALD - Hiccup And Lucky Dragons
Hiccup is the king of Viking village of Berk which is full of dragons. Like every year, Dragon War contest is going to be organized in Berk in which dragons fight till certain time limit and winning group of dragons are embraced asĀ lucky dragon group for the village. Each dragon is characterized by its unique power level Pi. There are N dragons in the village with each dragon having a power level in the range [1,N]. No two dragons have the same power level. Hiccup does not want Dragons to fight so he comes up with a new strategy to select the required group of Dragons. He tells the villagers the he had a dream last night in which his father told him that a group of dragons will be lucky for the village if following two conditions are satisfied:
- There are at least two dragons in the group.
- Difference in the power level of any two dragons in the group is at least two.
Hiccup is going to choose any random lucky group of dragons to avoid the Dragon War but first he wants to know how many such groups are possible.
Input
First line of input contains T i.e. number of test cases. Next T lines contains an integer N denoting number of dragons in the village followed by an integer M.
Output
Print (number of lucky dragon groups possible) % M for each N
Constraints:
1 <= T <= 100000
1 <= N <= 10^18
1 <= M <= 10^18
Example
Input: 2
1 3
3 2 Output: 0
1
Explanation of sample input, n = 3 and m = 2:
There will be 3 dragons with power level 1, 2, 3 respectively.
Only 1 group can be chosen i.e. {1, 3}. So answer is (1 % 2) = 1
hide comments
[Rampage] Blue.Mary:
2016-02-04 12:45:38
This problem is about constant optimization. |
|
reiji_azuma:
2015-07-18 16:58:27
O(T log n) is giving TLE. The time limit is way too strict. Not mentioning about the 10^18, due to it there is a need to use unsigned long long int which may lead in some solutions to WA. It's pretty pointless to give such a strict time limit. I would halve the T and make N <= 10^16, so that solutions slower than O(T log N) won't pass, but there are no problems with the type for input. Last edit: 2015-07-18 16:58:45 |
|
:.Mohib.::
2015-03-27 12:58:56
What is the answer for
|
|
Rajat De:
2015-03-24 12:00:37
time limit is way too strict |
|
RIVU DAS:
2015-03-23 19:15:10
The same solution which got accepted during the contest is giving TLE here. Any reasons?
|
Added by: | XeRoN!X |
Date: | 2015-03-22 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | Alkhwarizm 2015 |