| Submit | All submissions | Best solutions | Back to list |
EASYFACT - Easy Factorials |
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:) .
| 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 |
hide comments
|
||||||
|
2017-02-07 21:46:03 Michael Kharitonov
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 |
||||||
|
2016-10-26 23:09:04 Sifat Shishir
Got AC :) Last edit: 2016-10-27 17:48:04 |
||||||
|
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 |
||||||
|
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 |
||||||
|
2016-02-05 14:38:04 varun bumb
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 |
||||||
|
2015-10-31 21:43:48 varun bumb
@[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 |
||||||
|
2015-09-02 19:40:56 Pranav Rai
@admin I am getting a TLE - Can you suggest any improvements - http://www.spoj.com/submit/EASYFACT/id=14918201 |
||||||
|
2015-09-01 17:48:40 Arjav
@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 |
||||||
|
2015-08-30 13:09:38 Priyanshu Srivastava
15016491 - Please check this solution. I think it is giving correct answers for all cases. |
||||||
|
2015-08-30 00:14:06 Tejasv Gupta
@admin Please tell me whether my approach is correct or not moreover where else can I optimize it |
||||||
RSS