| Submit | All submissions | Best solutions | Back to list |
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
| 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 |
hide comments
|
2019-03-15 23:39:56 DK...
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 |
|
|
2015-07-27 18:37:22 Min_25
@underchange Please look at the constraints carefully. |
|
|
2015-07-27 11:25:30 underchange
@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? |
|
|
2015-05-18 18:50:01 [Lakshman]
Test cases are very strong, I have two different algorithm for which I got AC in DIVFACT3 in 1.4s here is giving WA. |
|
|
2015-05-15 02:25:30 Min_25
@Lakshman - Input #1, #2, #3: WA - Input #4, #5: TLE |
|
|
2015-05-14 07:09:36 [Lakshman]
@Min_25 Can you please help me, I am getting WA at First test Case But I Think my algorithm is correct. |
RSS