SPOJ.com - Problem BORING3

BORING3 - Boring Factorials (Ultimate)

no tags

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.

Submit solution!

hide comments

< Previous 1 2 Next >

	Min_25: 2016-06-10 09:11:28 Completed. :) =(Francky)=> Amazing !!! I'll try (next week) to make a master judge, in order to increase score when task is completed ! Congratulations ; you have no limit !!! Last edit: 2016-06-10 10:37:56
	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? Edit1: looks that in all Francky's problems the same engine is used so I won't be able to participate until I solve this WA problem. Last edit: 2014-07-24 09:33:49
	[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? --ans(Francky)--> I found your bug. You will easily check it using a brute force with an increasing D, and fixed p. lakshman-->still WA I have checked with my python code and Python got Ac here with same algo. --ans-->No, you have a little error on index in your pike code. I insist, check with a home_made_input with fixed p, and ascending D, I guess you will fail at 251. ;-) Lakshman-->really clueless about WA.I checked with, 250 to 502 with brute-force ,can you tell me what case 777 is? if possible. --ans(Francky)--> Curious, Your code should give WA to every D=1 mod 250 (execept D=1). You have a wrong index end check. I let you find it. You have a correct Python code. I'll try to make you the smallest wrong case. But you should have find it ; curious... Here is a small (not minimalist) counter example : 65501 1000000007. Another one : 10251 1000000007, and all wrong starting to this one (with D=1[250]). Lakshman--> Thanks Francky. Too many bugs in my initial code, all fixed only because of your Hint. Thanks. Last edit: 2014-04-11 05:35:30
	aqfaridi: 2014-03-14 20:53:48 i m getting WA when I set T = 100 and got Accepted when T = 60 ... why?? what is going wrong => id:11250703 and 11250679 --ans(Francky)--> Constraints are 0 <= D <= 10^6 @Francky ohh.. i was actually missing that D can be 0 also. Last edit: 2014-03-15 17:26:21
	[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. --ans--> There's a big warning on input format : it's not like in other BORING* problems, you have to make a little P-N. Last edit: 2014-03-09 17:29:11
	Francky: 2014-03-07 16:59:07 Done ! 32+30 = 62MB of IO uploaded. Have fun. Warning : the judge seems a bit slower with all those data !???!
	Francky: 2014-03-07 16:44:54 300000 100-digits prime generation done ! I will upload them and change description as proposed. Problem unavailable for a moment ; please be patient. (32MB of data)
	Aditya Pande: 2014-03-07 16:44:54 This seems real hard. --ans(Francky)--> You can try tons of ideas, there's plenty of rooms. It's really amazing. I was wondering how are you actually checking such large prime numbers ? --ans(Francky)--> Under ERH, we have some results to make deterministic some variant of Miller-Rabin primality test. That's all. Last edit: 2014-03-07 18:26:00

Submit solution!

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