SPOJ.com - Problem DIVFACT3

DIVFACT3 - Divisors of factorial (hard)

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 < 5432
1 < N < 10^8
1 < M < 10^9

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

Information

As it is possible to solve DIVFACT2 with fast language and intermediate method, here is the hard edition.
Warning : It could be very hard or impossible to solve this problem with slow languages.
Time limit is approx ×4 my unoptimized C_time. Good luck and have fun ;-) (Edit 2017-02-11 ; TL updated ; compiler changes)

Submit solution!

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

hide comments

2017-07-16 18:19:40
On codeChef onLine codecompile run , my code runs in 0.3s , here it says NZEC error , Any idea why?? same happened with DIVFACT2 , i used modified sieve still not working here:(

2017-05-05 05:34:55
can this be done by counting primes using segmented sieve? or some other algorithm is to be used?
=(Francky)=> No hint are provided here. Good luck.

Last edit: 2017-05-05 17:35:28

2017-02-10 00:23:25 Francky
@Michael :
It seems there's again some improvements with compiler/cluster.
"What Does The Fox Say?"'s code now end in 0.58s,
"Robert Gerbicz"'s code now in in 0.67s.
Yours is at 0.56s, as you'll can check. You have #1 !!!

(reply from Min_25)
It seems that gcc has been updated to 6.3.0 and its target has been changed to x86_64-linux-gnu. So, we can use 64-bit registers and can use int128_t.

=(Francky)=> Many thanks, Min_25. It will simplify and speedup some codes. It makes judge nearer from home machine ; at least for me.

@all : I don't know if rejudge of top 10 solutions for each languages and problems are scheduled. What do you think of such idea ? Please answer in forum section, in appropriate place.

Last edit: 2017-02-10 22:39:35

2017-02-07 21:03:31 Michael Kharitonov
Clang is much faster than GCC for my algorithm, maybe because GCC is much older.
Francky, can you rejudge "What Does The Fox Say?" and "Robert Gerbicz" fastest submissions or at least resubmit and tell me their new times.
By the way, problem EASYFACT is almost exactly the same.

=(Francky)=> We can't rejudge at this time.
"What Does The Fox Say?"'s code now end in 0.64s
"Robert Gerbicz"'s code now in in 0.78s.
And I know EASYFACT is almost the same... I've told several times psetter that easytask(Hardtask(x)) isn't interesting when Hardtask(x) already exists...

Last edit: 2017-11-21 12:17:27

2015-02-16 09:11:18 mehmetin
I solved the problem, but with a huge amount of memory and not with a really fast time. Can some hint or useful link be given about the prime count method mentioned below?

(Francky) => an obvious hint is that cache memory is way faster than RAM, so segmented work can be much faster than big_block work ; it's true it's harder to write it. Good luck.

Last edit: 2016-06-07 11:14:13

2015-01-30 09:08:57 ISHANI
I am very excited for the next version of DIVFACT(Min_25 do it fast).enjoyed solving it~~~~~.
--Francky--> It seems you maybe provide your solution to spoj_TK, if true : do you really think it's a good idea ??? Have you any guaranty on what could happen due to this ?
--ISHANI-->sorry franky,but i upload my solution on spoj toolkit bcz user can't see code.i think they use spoj toolkit for input/output confirmation.but if u are saying that this is wrong work then i'll never upload my code on spoj_Toolkit after today.By the way Franky, spoj Toolkit belongs to spoj so what's wrong in uploading on spoj Toolkit??

--ISHANI-->Ok Franky, now i understood.after searching i found that spoj Toolkit is a user on spoj.so i'll never upload my code on spojToolkit.

Last edit: 2015-01-30 20:58:04

2015-01-27 10:24:24 :(
@rohith... Thanks a ton for helping me out.. :)

Last edit: 2015-01-27 14:28:35

2015-01-22 11:53:16 Min_25
I would like to propose a little different constraint such as (T < 5.432, N < 10^11 and M < 10^12).

--Francky--> Honor is yours ; great to see a very new challenging task. The better is maybe to put DF2 in tutorial, and wait your edition.

Last edit: 2015-01-22 12:12:24

2015-01-22 10:42:06 Francky
@Lakshman : Fine, very good. I was thinking at that problem again ; DF2 and DF3 are too near, I build them very quickly. I think setting an extreme edition, or change constraints here. As we don't like to change constraints, I think put DF3 in tutorial and set DF4 harder. The fact is almost everybody got the whole idea for DF2 and got AC for DF3 by the way (except one ;-) ).

¿ What AC users think about :
* moving DF3 to tutorial
* set DF4 harder in classical. (more test cases)

2015-01-22 09:13:18 [Lakshman]
@Francky. Yes it is possible with python(PYPY).