BDOI16B - Beautiful Factorial Game
The statement of this problem is very simple. Given two number n and k, you need to find the maximum power of k (i.e. x) such that n! % kx = 0. Here n! is the notation of n factorial. If you are not familiar with the notation,
n! = 1 * 2 * 3 * 4 * 5 * 6 ... * n
Input
First line of the input will contain an integer t (1 ≤ t ≤ 20) denoting the number of test case. The next t lines contain two integer number n and k as described above.
Constraints
For easy version, 1 ≤ n ≤ 10, 2 ≤ k ≤ 10
For harder version, 1 ≤ n ≤ 100000000, 2 ≤ k ≤ 100000000
Output
For each test case, print “Case t: x” where t is the test case number and x is the maximum power of k for which n! % kx = 0.
Example
Input: 2 5 2 1000 2 Output: Case 1: 3 Case 2: 994
Explanation
In the first test case, n = 5 and k = 2. So, n! = 120.
- 120 % 20 = 0
- 120 % 21 = 0
- 120 % 22 = 0
- 120 % 23 = 0
- 120 % 24 = 8
- 120 % 25 = 24
- 120 % 26 = 56
- 120 % 27 = 120
So, the answer should be 3.
Problem Setter: Rakibul Islam
hide comments
cyclic_func:
2017-01-07 10:00:13
C.a Last edit: 2017-01-07 10:08:05 |
|
aman224:
2016-11-28 14:37:05
AC!!! Last edit: 2016-11-29 00:03:37 |
|
[Lakshman]:
2016-10-07 22:09:08
There is already a problem with better constraints http://www.spoj.com/problems/GCPC11A/ |
|
wisfaq:
2016-10-07 14:59:35
For easy version, 1 <= n <= 10, 2 <= k <= 10
|
|
Sushovan Sen:
2016-10-06 20:42:18
Test cases are very weak. Please add some more. |
Added by: | Rezwan |
Date: | 2016-10-05 |
Time limit: | 1s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 GOSU |
Resource: | Bangladesh Olympiad on Informatics 2016 National; Problem Setter: Rakibul Islam |