SPOJ.com - Problem DIVFACT2

DIVFACT2 - Divisors of factorial (medium)

Factorial numbers are getting big very soon, you'll have to compute the number of divisors of such highly composite numbers.

Input

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

Output

Output T lines, one for each test case, with the number of divisors of the factorial of N.
Since the answer can get very big, output it modulo M.

Example

Input:
3
2 1000
3 11
4 5
Output:
2
4
3

Constraints

0 < T < 512
1 < N < 10^8
1 < M < 10^9

For N, M : uniform random input in the range.
One input file.

Information

Time limit is sqrt(T_good.py × T_bad.c). It implies that you can solve it with some interpreted languages with correct algorithm without any optis, but will get TLE with fast languages and non optimal algorithm.
Good luck and have fun ;-)

(Edit 2017-02-11 : TL updated ; compiler changes)

Submit solution!

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

hide comments

2021-07-09 11:45:07
I would be very grateful to the author, if he can tell the mistake in my code.
Submission ID: 28171836
Thank you

=(Francky)=> It is easy to build some test cases with some brute semi-brute-force.

Last edit: 2021-07-14 00:47:47

2017-07-16 11:53:18
Any hints for this problem ?? i give up

2016-04-03 16:22:52
@francky can you plese provide some test case
i am getting wrong answer

Last edit: 2016-04-04 12:40:39

2016-03-18 21:05:25
I solved by precomputing all prime numbers less than 10^8 then determining no. of divisors but still getting TLE ....
No idea .... Getting frustated

2016-03-17 17:26:38 shikhar jindal
not getting any idea how to solve this :( ...what other concepts are needed along with the lagrange's theorem..thanks in advance :)

=(Francky)=> That's the problem, and you have to figure it out. Good luck.

Got it...used same code for divfact2 and divfact3 and got accepted...feeling happy...btw very nice problem./\
For all those not getting any idea and are at the verge of giving up...look at the pattern that occur in the prime factorisation of large factorials...such as 50!, 100!.

Last edit: 2016-03-18 11:05:30

2015-06-08 12:17:34 Maroof
Why this problem isn't showing on the list of solved problems? .. BTW awesome problem. Learnt a lot of things to optimize the code :)

=(Francky)=> Because, it's a tutorial problem. The classical, with harder constraints is here.
Good luck, and thanks for the appreciation.

Last edit: 2015-06-08 15:28:07

2015-02-11 14:08:11 Sayak Haldar
Francky, would I get an AC if I precompute all the prime nos less than 10^8 then use (n)1/2(logn) per query?

(Francky) => Yes, it's the easiest method, I think.
Francky, Thank you...:)

Last edit: 2015-03-09 21:07:30

2015-01-30 17:41:09 Francky
Now there's DIVFACT4, it's time to move this one to tutorial, as almost every submission got AC with both (DF2, DF3) without any change.
Good luck for DIVFACT4 !
Thanks to Min_25 for this new extreme task.

Last edit: 2015-01-31 01:46:49

2015-01-24 12:19:43 rohith
@Francky my code works absolutely fine but still WA
any corner cases please ;( spent countless hours complexity (n^1/2)*log(n)

--Francky--> If you can solve DIVFACT then you will easily find corners cases by your own, as your code gives almost only WA. Good luck.

@Francky Finally AC just a small arithmetic mistake ;D :D

Last edit: 2015-01-26 05:00:59

2015-01-19 07:58:25 [Lakshman]
Enjoying this!! Getting closer to abdou_93 Trying for first place..........Taken first place!!!

ans(abdou)->well done . :D

ans(Francky)--> Congrats for the first Python AC.

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

Last edit: 2015-01-23 11:28:39