SPOJ.com - Problem EASYFACT

EASYFACT - Easy Factorials

#number-theory #factorial

Finding factorials are easy but they become large quickly that is why Lucky hate factorials. Today he have another task related to factorials.

For a given number n how many ways factorial n can expressed as a sum of two or more consecutive positive integers. Can you help lucky ?

Input

First line contains single integer T < 5001, next T lines followed by an integer N<10^8 and M<10^9.

where M is a prime number.

Output

Print the desired result mod M.

Example

Input:
1
3 7

Output:
1

Explanation:: 3! = 1+2+3 only one way.

Speed Adicts My best time for all cases is 1.57s. Best of Luck have fun:) .

Submit solution!

hide comments

< Previous 1 2 3 Next >

	Michael Kharitonov: 2017-02-07 21:46:03 Lakshman, I've beaten your time:) This problem is quite similar to DIVFACT3 ==(Lakshman)==>Congrats "Michael Kharitonov" your code is quite fast, With new Cluster My old code runs in .96s. Last edit: 2017-02-08 07:16:13
	Sifat Shishir: 2016-10-26 23:09:04 Got AC :) Last edit: 2016-10-27 17:48:04
	cena_coder: 2016-07-13 08:08:14 now it is working up n<=10^6 and then TLE shit man :( =(Lakshman)=>Some suggestion 1. Do not compute prime every time just precompute once and use it. Last edit: 2016-07-14 05:31:51
	cena_coder: 2016-07-06 06:54:56 i can't understand why it is showing WA Admin can u check it out for me id 17232977 ==(Lakshman)=>Because your solution is wrong. Last edit: 2016-07-06 17:51:53
	varun bumb: 2016-02-05 14:38:04 FINALLY, GREEN!! Took 6 months to figure out the mistake BTW, Awesome Problem. Advice: Try to minimize the use of long long and mod ==>Good Job. Last edit: 2016-02-08 05:52:22
	varun bumb: 2015-10-31 21:43:48 @[Lakshman] : Now my code is working fine for small inputs as well still i'm getting WA. Can you check my code. Code id: 15518033
	Pranav Rai: 2015-09-02 19:40:56 @admin I am getting a TLE - Can you suggest any improvements - http://www.spoj.com/submit/EASYFACT/id=14918201
	Arjav: 2015-09-01 17:48:40 @Admin after too much struggle my solution get ac in 10.72 ...........need to know much more optimisations that u would have probably used... ==(Lakshman)=> My algorithm is not only depends upon optimization tweaks but also have better complexity. Some suggestion:1.Use unsigned prime array.(Segmented sieve is much faster)2.Reduce mod operation.3.fast IO. Last edit: 2015-09-02 05:56:12
	Priyanshu Srivastava: 2015-08-30 13:09:38 15016491 - Please check this solution. I think it is giving correct answers for all cases.
	Tejasv Gupta: 2015-08-30 00:14:06 @admin Please tell me whether my approach is correct or not moreover where else can I optimize it

Submit solution!

Added by:	[Lakshman]
Date:	2015-05-13
Time limit:	5s-10s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 JS-MONKEY