| Submit | All submissions | Best solutions | Back to list |
DCEPC11B - Boring Factorials |
Sameer and Arpit want to overcome their fear of Maths and so they have been recently practicing Maths problems a lot. Aman, their friend has been helping them out. But as it goes, Sameer and Arpit have got bored of problems involving factorials. Reason being, the factorials are too easy to calculate in problems as they only require the residue modulo some prime and that is easy to calculate in linear time. So to make things interesting for them, Aman - The Mathemagician, gives them an interesting task. He gives them a prime number P and an integer N close to P, and asks them to find N! modulo P. He asks T such queries.
Input
First line contains an integer T, the number of queries asked.
Next T lines contains T queries of the form “N P”. (quotes for clarity)
Output
Output exactly T lines, containing N! modulo P.
Example
Input: 3 2 5 5 11 21 71 Output: 2 10 6
Constraints
1 ≤ T ≤ 1000
1 < P ≤ 2×109
1 ≤ N ≤ 2×109
Abs(N-P) ≤ 1000| Added by: | dce coders |
| Date: | 2013-10-01 |
| Time limit: | 1s |
| Source limit: | 50000B |
| Memory limit: | 1536MB |
| Cluster: | Cube (Intel G860) |
| Languages: | C CSHARP C++ 4.3.2 CPP C99 HASK JAVA PAS-GPC PAS-FPC PYTHON PYTHON3 PY_NBC |
| Resource: | Own Problem |
hide comments
|
|||||||||
|
2022-08-26 10:26:12
Avoid lots of modulo operations, as they consume time and result in TLE. |
|||||||||
|
2021-01-11 16:23:52
This is a great problem of(wilson+fermit) theorem Last edit: 2022-07-20 11:56:43 |
|||||||||
|
2020-09-25 14:10:39
good ques wilson n little fermat my ans for test case 1999554444 1999555444: 502781432 Last edit: 2020-09-26 10:52:23 |
|||||||||
|
2020-09-25 10:46:09
more testcases: 10 780 653 54 601 210 659 780 659 776 617 678 617 1110 631 1182 631 219 617 551 607 output: 0 1 581 0 0 0 0 0 503 509 |
|||||||||
|
2020-09-02 18:21:09
don't use code from cp-algorithm.. search for compute n!modulo p gfg.. all the best for AC |
|||||||||
|
2020-07-15 20:18:53
There's something strange about the judge used here, wasted half an hour yesterday because an assert on n < p wouldn't trigger a NZEC. Tried without looking up anyone else's theorem several times last few years, had to give up on that but still passed with logic more straightforward than what others seem to be doing. |
|||||||||
|
2020-06-14 18:43:36
My code is giving TLE, although I used the same algorithm given at CP-Algo page, including the condition when (n>=p). What's the method to remove that TLE? |
|||||||||
|
2020-04-26 03:00:10
Willson thoerem+check when n is greater than p then n goes up to p-1 then modulo multiplicative inverse |
|||||||||
|
2019-07-29 12:48:35
ac in five go . dont use recusive fast modulo , use iterative |
|||||||||
|
2019-07-04 11:51:15
ac in one go |
|||||||||
RSS