SPOJ.com - Problem SMALLM

SMALLM - Smallest Number (medium)

no tags

60 is divisible by 2, 3, 4 and 5. No smaller number than 60 has this property.

Input

On the first line, you will be given two integers T (the number of test cases), and M (an integer).
Each of the next T lines contains an integer N.

Output

For each test case, output on one line, the smallest number that is divisible by all integers from 1 to N (inclusive).
As the answer may be a big number, output it modulo M.

Example

Input:
1 1000000007
5

Output:
60

Constraints

T <= 10^5

10^8 <= M <= 2×10^9, a prime number

0 < N < 10^8

Information

There's one easy input file, and several harder ones. Time limit allows unoptimized code with fast languages to get AC ; for slower languages it may be hard.
Good luck and have fun ;-)

Edit(2017-02-11) : New time limit (after compiler changes).

Submit solution!

hide comments

< Previous 1 2 Next >

	aj_254: 2019-05-19 21:00:53 @nadstratosfer role mode for me :) python master
	nadstratosfer: 2019-05-19 19:27:15 I've had 999 problems and this wasn't one of them.. until now! Actually, I've prototyped this in Python 2 days ago (would need TL ~ 11s to AC in PyPy :/) but held back with implementing in C for this special occasion. Great problem but I'll have to revisit once I finally get the core routine needed here out of my to-do-in-C list. My SPOJ streak of no day without a submission since 2017-09-04 will probably get broken by an upcoming holiday; shame as I sustained it through good and worse, even quickly solved some tutorial task right before taking my wife to the hospital when my daughter got born last year.. It will feel good to turn off the computer having this one under my belt though =) =(Francky)=> Special congrats ! I really appreciate the honor made in comment. Last edit: 2019-06-11 22:32:26
	Bhuvnesh Jain: 2016-11-02 12:10:50 @Francky, any hints on how I can further speed-up my solution (Submission ID : 18083628)? Last edit: 2016-11-02 12:13:05
	ashish kumar: 2015-12-25 12:22:35 How can I fast up my code it gives AC on 11 sec. Any suggestion.
	Sayak Haldar: 2015-07-15 04:21:56 Francky,could you please do me another favour? Could you please tell me what is the actual result fro N=100 and M=1000000007. I tried normal modulo based calculation (multiplication) as well as modular arithmetic related multiplication method depicted in wikipedia. Now, I am uncertain which one is the actual result for N=100 and M=1000000007 =(Francky)=> No other case is provided. I don't do that to any problem. I am really sorry for asking it. However, I managed to solve the problem. Last edit: 2015-07-15 21:16:52
	Sayak Haldar: 2015-07-14 22:12:28 Francky: could you please check my solution with solution id 14669671? Does it contain too many WAs? also, does this solution generate TLE for any particular case? Also, what is answer of N=0? =(Francky)=> Few WA ; I can't be sure (I'm not at home) ; N=0 is excluded by constraints. Good luck. Last edit: 2015-07-14 23:21:45
	Sayak Haldar: 2015-03-06 13:48:12 Francky, what is the needed time complexity for this problem? (Francky) => Most of the time needed complexity isn't provided. According to number of testcases, you can guess if your method will be fast enough or not. Good luck. Last edit: 2015-03-06 18:14:46
	dark king : 2015-02-25 19:05:47 1 second is approx. how many operations?
	Adarsh kumar: 2015-02-24 21:46:48 Same code passes for SMALL ... but here gives WA ... unable to figure out :( (Francky) => You have few WA, good luck. Last edit: 2015-02-24 23:27:45
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2015-02-20 00:50:41 @Francky: Something curious happen, why my submission (ID:13696685) getting WA but (ID:13696680) got AC? The difference is just at line 22, it should not affect the verdict if the judge used is not exact right? strange.. (Francky) => I agree it's curious! As the judge is 1. Ignore extra whitespaces. Very curious. I let your report the bug (your input start by 112 extra new empty lines, and that make you AC, without WA although your output is exactly the answer !!!), I can give you more details if you ask. EDIT : mail with some more infos sent to you and admin. Hope this will help. Last edit: 2015-02-20 01:35:16

Submit solution!

Added by:	Francky
Date:	2015-01-24
Time limit:	0.5s-2s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64 JS-MONKEY
Resource:	SMALL