FACTMODP - Factorial Modulo Prime
Find $N!$ modulo $P$.
Input
The first line contains $T$ ($1 \le T \le 100,000$), the number of test cases.
Each of the next $T$ lines contains two integers $N$ ($0 \le N \le 10^{11}$) and $P$ ($2 \le P \le 10^{11}$), where $P$ is a prime.
Output
For each $N$ and $P$, output $N!$ modulo $P$.
Constraints
For each input file, It is guaranteed that (the sum of $\sqrt{P}) \le 320000$.
Example
Input
3 1000 9907 1000000 9999907 10000000000 99999999907
Output
4494 3354924 40583077821
Note
- Probably, $O(P)$ solutions will not pass.
- Intended solutions have a complexity of about $O(\sqrt{P} \log{P})$
- My solution runs in 0.5 seconds for each input file.
hide comments
Min_25:
2017-11-09 14:37:42
@Michael Kharitonov
|
|
Michael Kharitonov:
2017-11-09 13:22:52
Let M(n) be the time to multiply 2 polynomials of degree n in Z/PZ. Then M(n)~n*log(n)*log(nP)
|
Added by: | Min_25 |
Date: | 2017-10-20 |
Time limit: | 10s-15s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All |