GCPC11A - Faculty Dividing Powers
Fred Faculty and Paul Power love big numbers. Day after day Fred chooses a random integer n and he computes n!. His friend Paul amuses himself by computing several powers of his randomly chosen integer k like k2, k3 and so on. On a hot summer day, Fred and Paul got really, really bored, so they decided to play a joke on their buddy Dave Divider. Fred chooses a random integer n while Paul chooses a random integer k. They want Dave to find the biggest integer i such that ki divides n! without a remainder, otherwise they will throw a cake in Dave's face. Because Dave does not like cakes in his face, he wants you to help him finding that integer i.
Input
The first line contains the number of test cases t (1 ≤ t ≤ 100). Each of the following t lines contains the two numbers n,k (2 ≤ n ≤ 1018, 2 ≤ k ≤ 1012) separated by one space.
Output
For each test case, print the maximum integer i on a separate line.
Example
Input: 2 5 2 10 10 Output: 3 2
Be careful with overflows in this problem (use 64 bit integers, avoid multiplications which will lead to overflow).
hide comments
|
Adrian Kuegel:
2012-03-26 12:13:37
@Akash: please read the warning, and check each line of your code! I saw it with one short look that you can get overflows! |
|
Akash Bansal:
2012-03-25 17:34:26
i m getting ans at the highest limit too still WA :( Last edit: 2012-03-25 17:35:07 |
|
The new guy:
2011-11-11 06:30:55
@Adrian - Can you please let me know where does 6005728 submission id give WA, it works for the extreme cases fine. :( |
|
Chandan Giri:
2011-10-31 14:02:56
finally :) |
|
|
Adrian Kuegel:
2011-07-22 10:33:29
@panny: you did not understand what I mean; your algorithm is O(sqrt(k) * log(n)), you can achieve O(sqrt(k) + log(n)). |
|
Piyush :
2011-07-22 10:05:00
@adrian : sir did it still slow ... id :5415613 . thanks |
|
|
Adrian Kuegel:
2011-07-20 07:39:16
@panny: think about it which part of k is relevant to compute the answer. |
|
|
Adrian Kuegel:
2011-07-14 07:39:01
@all: I will not answer any more comments about programs getting WA because of overflow; there is now a clear warning at the end of the problem, and I mentioned also how to avoid this mistake. Last edit: 2011-07-22 10:35:08 |
|
|
Adrian Kuegel:
2011-07-12 13:01:34
To check if a * b will lead to overflow, check if a > (2^63-1) / b. |
|
|
Adrian Kuegel:
2011-07-12 13:01:34
@Akshay: you call gogo with k, which can be a value > 2^31-1, so the parameter N of gogo needs to be a long long. |
| Added by: | Adrian Kuegel |
| Date: | 2011-07-05 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | All except: ASM64 |
| Resource: | German Collegiate Programming Contest 2011 (Authors: Christopher Dennl and Thomas Fersch) |
RSS