SPOJ.com - Problem SMALLM

SMALLM - Smallest Number (medium)

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!

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

hide comments

2015-01-29 08:28:22 [Lakshman]
I am curious to know how this problem can be done in in less than 4 mb. Is there any formula? or some different method for this, I have reduced this problem to O(sqrt(sqrt(n))) But still ...But still can't get any idea of any algorithm that takes less than 50 MB. @Francky if you find this comment spoiler you can delete it or you can hide(as you wish).

--Francky--> The use of memset can hide the real memory used by a program, so you can only know the minimum memory used at start by other users ; perhaps they use more, perhaps less...

--wisfaq-->In Pascal you can use dynamic arrays. The memory is assigned on the heap rather than on the stack and freed before the program ends.
SPOJ isn't able to report this memory used.
So it's dangerous to rely on the reported memory by SPOJ as a spoiler for the algoritm used.

--(Lakshman)-->Thanks @Francky and @wisfaq.

Last edit: 2015-01-29 11:15:36

2015-01-26 18:54:29 sourav
can we take an array of long long of size 5*10^7..bcoz i m getting sigkill re

Last edit: 2015-01-26 18:56:23

2015-01-26 03:36:04 [Lakshman]
@Francky Can please tell me if I am getting TLE in all input files or only in hard one. Thanks.
--Francky--> You have TLE on hard ones. And AC on SMALL-like input. (hopefully ;-) ) Good luck.

--Lakshman-->Finally Accepted ;)

Last edit: 2015-01-26 13:52:44

2015-01-25 19:27:51 ISHANI
My complexity is O(n)+t*O(1).still getting TLE.Francky,is it enough or not?

--Francky--> Your complexity is not that you described. You got TLE even on the easy input file.

--ISHANI-->I used Sieve of Atkin ,which is in o(n) and simple o(n) loop.is it bcz of mod of long long intege?can u please see my code

Last edit: 2015-01-26 18:09:20

2015-01-25 15:50:27 [Lakshman]
My complexity in worst case is T*2400*log(n) + some pre-computation is it no enough to pass the time limit.

2015-01-24 20:36:47 Francky
Congrats to Mitch as the first solver.

(Mitch) Thanks!

Last edit: 2015-01-24 21:00:18

2015-01-24 18:46:19 Francky
I tried an edition possible with N<10^18 (using a simplification by some primorial), but in fine it was too artificial, so I propose a 10^8 edition, with fixed modulo given in input.

Good luck.