BORING3 - Boring Factorials (Ultimate)
Factorial is one of the most attractive word this week, it is proposed to reload a famous problem. Is it so boring ? As the reload edition wasn't hard enough, we'll make a challenge edition with harder constraints. 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 (not so) close to P, and asks them to find N! modulo P. He asks T such queries.
Input
The input contains several lines. Probably, you'll can't process all ; please exit your program before the time limit. Warning : To allow more input, its presentation is different than in other BORING* problems. On each line, your are given two integers D (delta), and P a prime number.
Output
For as many test cases you can, you have to print (P-D)! modulo P.
Example
Input: warning, it's different from other BORING* input. 3 5 6 11 50 71 [...]
Output: 2 10 6 [...]
Constraints
0 <= D <= 10^6 1 < P < 10^100, a prime number
For your information : With Python3, my "brute force" got 435 points, my first code for (BORING1/2) got 1631 points ; my new BORING3 code got 2772 (edit 4041) points to be challenged. ;-) Have fun.
Edit(12/II/2017) Now the MasterJudge takes time into account if you reach the limit of input file : There's only 300000 lines.
hide comments
Min_25:
2016-06-10 09:11:28
Completed. :)
|
|
Maciej Misiak:
2014-07-22 13:29:57
@Lakshman: but it won't help me. I've submitted empty file expecting status ACC and 0 points. Instead I've got WA. Why?
|
|
[Lakshman]:
2014-07-21 16:31:38
@Maciej Misiak You can try this easy version with only 100 test cases http://www.spoj.com/problems/DCEPC11B/ |
|
Maciej Misiak:
2014-07-21 15:58:57
What output should the program print in case I exit after e.g. 10 tests? I get WA on program not printing anything. |
|
[Lakshman]:
2014-04-10 08:47:37
@Francky for what kind of case my new PIKE code is failing?
|
|
aqfaridi:
2014-03-14 20:53:48
i m getting WA when I set T = 100 and got Accepted when T = 60 ... why??
|
|
[Lakshman]:
2014-03-09 16:15:01
@Francky with my new python code and 1 test case here I am getting TLE but it is working perfect on my system, and giving result in less than 1 second.
|
|
Francky:
2014-03-07 16:59:07
Done ! 32+30 = 62MB of IO uploaded. Have fun.
|
|
Francky:
2014-03-07 16:44:54
300000 100-digits prime generation done !
|
|
Aditya Pande:
2014-03-07 16:44:54
This seems real hard.
|
Added by: | Francky |
Date: | 2014-03-04 |
Time limit: | 60s |
Source limit: | 50000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | All except: ASM64 |
Resource: | DCEPC11B |