The Factorial Conundrum
All submissions for this problem are available.
Little Omrita recently learned about factorials. Her teacher gave her a list of factorials of all the numbers starting from 1 to N. Omrita can choose any integer M, and she is supposed to compute the product of all the factorials starting from 1 i.e (1! * 2! * 3! * 4! * …) modulo M.
During her calculation, she noticed that no matter what M she choose before (at the start of the process) after a certain number of multiplication the answer becomes 0 and hence she can’t continue further.
She don't like this and wanted to know: for a chosen M what could be the maximum number of products she can compute before she has to stop. (See example for more clarification).
The first line of the input contains an integer T denoting the number of test cases. The description of T test cases follows.The first and the only line of each test case contains a single integer M denoting the number omrita had chosen.
For each test case, output a single line containing the required answer.
- 1 ≤ T ≤ 100
- 1 ≤ M < 1020
- 1 ≤ N < 1030
Input: 1 10 Output: 4
For the test case M = 10; First few terms in Omrita's list:
1! = 1
2! = 2
3! = 6
4! = 24
5! = 120
6! = 720
7! = 5040
8! = 40320
Omrita will proceed in the following manner:
1 * 2 = 2 MOD 10 = 2
2 * 6 = 12 MOD 10 = 2
2 * 24 = 48 MOD 10 = 8
8 * 120 = 960 MOD 10 = 0
So, she can perform 4 calculations.
|Time Limit:||1.12448 sec|
|Source Limit:||50000 Bytes|
|Languages:||C, CPP14, JAVA, PYTH, PYTH 3.5, CS2, PAS fpc, PAS gpc, RUBY, PHP, GO, NODEJS, HASK, SCALA, D, PERL, FORT, WSPC, ADA, CAML, ICK, BF, ASM, CLPS, PRLG, ICON, SCM qobi, PIKE, ST, NICE, LUA, BASH, NEM, LISP sbcl, LISP clisp, SCM guile, JS, ERL, TCL, PERL6, TEXT, CLOJ, FS|
Fetching successful submissions
If you are still having problems, see a sample solution here.