BDOI16B  Beautiful Factorial Game
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! % k^x = 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! % k^x = 0.
Sample Input 
Output of sample input 
2 5 2 1000 2 
Case 1: 3 Case 2: 994 
Explanation of the sample:
In the first test case, n = 5 and k = 2. So, n! = 120.
n! % 2^0 = 0
n! % 2^1 = 0
n! % 2^2 = 0
n! % 2^3 = 0
n! % 2^4 = 8
n! % 2^5 = 24
n! % 2^6 = 56
n! % 2^7 = 120
So, the answer should be 3.
Problem Setter: Rakibul Islam
hide comments
cyclic_func:
20170107 10:00:13
C.a Last edit: 20170107 10:08:05 

aman224:
20161128 14:37:05
AC!!! Last edit: 20161129 00:03:37 

[Lakshman]:
20161007 22:09:08
There is already a problem with better constraints http://www.spoj.com/problems/GCPC11A/ 

wisfaq:
20161007 14:59:35
For easy version, 1 <= n <= 10, 2 <= k <= 10


Sushovan Sen:
20161006 20:42:18
Test cases are very weak. Please add some more. 
Added by:  Rezwan 
Date:  20161005 
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 