SMALLM - Smallest Number (medium)

no tags 

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


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.


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.


1 1000000007


T <= 10^5
10^8 <= M <= 2×10^9, a prime number
0 < N < 10^8


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).

hide comments
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.

:.Mohib.:: 2015-07-23 12:02:00

Last edit: 2015-07-23 12:40:01
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

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