DIVFACT4 - Divisors of factorial (extreme)
Find the number of divisors of N! (factorial) very fast !
Input
The first line contains an integer T, the number of test cases.
Each line of the next T lines contains two integers N and M.
Output
For each line, output a single line containing the number of divisors of N! modulo M.
Example
Input
3 10 989 10000 999989 10000000000 999999999989
Output
270 616797 40946947081
Constraints
1 ≤ T ≤ 104
0 ≤ N ≤ 1011
1 ≤ M ≤ 1012
Information
There are 5 input files.
- Input #1: T ≤ 104, N ≤ 104, TL = 1s
- Input #2: T ≤ 5, N ≤ 108, TL = 20s
- Input #3: T ≤ 5, N ≤ 109, TL = 20s
- Input #4: T ≤ 5, N ≤ 1010, TL = 20s
- Input #5: T ≤ 5, N ≤ 1011, TL = 20s
My total running time is 3.14 sec. (C++)
Credits
- ivar.raknahs - the original problem (DIVFACT) author
- Francky - the author of DIVFACT2 and DIVFACT3
hide comments
DK...:
2019-03-15 23:39:56
Very nice problem, take care about all your variables. it could be overflow is some testcases, so take mod(m) all of them, this cost me several WA's |
|
Min_25:
2015-07-27 18:37:22
@underchange
|
|
underchange:
2015-07-27 11:25:30
@Min_25 I submitted my AC program for DIVFACT3 to DIVFACT4, but it get WA on input #1. Input #1: T ≤ 10^4, N ≤ 10^4, is even weaker than DIVFACT3. Is there something wrong with this input or this constraint? |
|
[Lakshman]:
2015-05-18 18:50:01
Test cases are very strong, I have two different algorithm for which I got AC in DIVFACT3 in 1.4s here is giving WA. |
|
Min_25:
2015-05-15 02:25:30
@Lakshman
|
|
[Lakshman]:
2015-05-14 07:09:36
@Min_25 Can you please help me, I am getting WA at First test Case But I Think my algorithm is correct. |
Added by: | Min_25 |
Date: | 2015-01-30 |
Time limit: | 1s-20s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 JS-MONKEY |
Resource: | DIVFACT |