FACTMODP - Factorial Modulo Prime
Find modulo .
Input
The first line contains (), the number of test cases.
Each of the next lines contains two integers () and (), where is a prime.
Output
For each and , output modulo .
Constraints
For each input file, It is guaranteed that (the sum of .
Example
Input
3 1000 9907 1000000 9999907 10000000000 99999999907
Output
4494 3354924 40583077821
Note
- Probably, solutions will not pass.
- Intended solutions have a complexity of about
- 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 |