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 >

	varun bumb: 2015-08-09 00:02:33 @Lakshman,can you please check my code.id = 14852186. =(Lakshman)=>Sorry I did not see your comment, Check your code for small inputs Eg. [1 to 100] Last edit: 2015-08-15 08:36:37
	Vivek Mangal: 2015-07-08 15:09:02 @admin i am beginner.can u pls check my code.id=14625920. =(Lakshman)=> The code id you have mention have wrong answer for both Input files. code.id::14624067 Accepted for small inputs but TLE for large input file. If you are beginner you should try other problems first, there are many more. You algorithm is correct but too naive to AC here. Good Luck. Last edit: 2015-07-09 05:30:36
	Soma: 2015-07-04 02:14:26 @[Lakshman] : can you check my code and tell me what other optimisations i can make in the code. my code now runs in 3.25s but your able to solve it even faster (as your note at the end says). code id :14596189 =(Lakshman)=> 1.sieve() yours .50 mine .13 Second part which you are doing in sqrt mine is approx n^.33~.38 and third part I am doing in (constant) * (lon n)^2. Which makes my code faster. (Soma): thanks for the hints. by the way nice problem. Last edit: 2015-07-04 18:19:09
	saksham agrawal: 2015-06-22 19:20:54 @admin..Please help.. do check my code.. --(Lakshman)-->Your algorithm is completely wrong! Last edit: 2015-06-22 21:07:17
	Marko Puza: 2015-06-15 01:35:26 Very nice problem. I am the first to solve it with Java, so I am really excited. --(Lakshman)--->Good!! Last edit: 2015-06-15 09:30:33
	black MaMbA: 2015-06-14 09:31:42 @Lakhsman,would you please tell me if my approach is correct or not --(Lakshman)->Yes @Lakshman,I know i can improve upon the p*e hint you have given but do i need to work on other aspects too like the heart of the problem which requires iterations as a one liner to compute that is not possible as far as i have tried.your problem is great and DON'T NEED ANY SPOILERS.little help :) ==(Lakshman)=> Sorry for replying late, I did not saw your comment. In order to solve this you need at least SQRT order of algorithm. Last edit: 2015-07-20 13:32:47**
	Akashdeep Goel: 2015-06-13 12:53:44 @admin:- Please check whether my approach is correct and also how many test cases i am failing..:-( --(Lakshman)-->You have many correct answer. Best of luck. Last edit: 2015-06-13 17:41:55
	[Lakshman]: 2015-06-12 11:54:11 @ADITYA PRAKASH Based on submission 14436796 Your code works fine for small cases but RTE in large one.
	ADITYA PRAKASH: 2015-06-11 20:04:01 @admin is my approach correct?
	gamer496: 2015-06-11 01:03:15 @admin is my approach correct? --(Lakshman)--> Yes for small input file your code works fine. Last edit: 2015-06-11 17:07:38

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