SPOJ.com - Problem IRECSQRT

IRECSQRT - Inverse of Recurrence Problem With a Square Root

no tags

Given this recurrence formula (be careful, it's in inverse form):

Given n (0 ≤ n < 2⁶⁴) and m (0 < m < 2⁶⁴), your task is to compute a_n modulo m.

It's guaranteed that a_n is always an integer.

Input

First line containing an integer T (0 < T ≤ 5×10⁴), than T cases follow.

For each test case there are two integers n and m, written in one line, separated by a space.

Output

For each test case, output the required answer: a_n modulo m.

Example

Input:
10
0 10
1 10
2 10
3 10
10 10
100 100
1000 1000
10000 10000
100000 100000
9876543210123456789 1234567890987654321

Output:
1
2
5
5
5
51
251
6251
6251
657422418465782775

Time limit ~7x My program speed: Click here to see my submission history and time record for this problem

Submit solution!

hide comments

< Previous 1 2 3 Next >

	Dune: 2019-12-31 13:09:38 AC in python and pypy without wolfram nor OEIS, 10 lines of python code.
	noble_mushtak: 2019-06-23 19:42:52 Very easy to solve using WolframAlpha, OEIS, and Python! Using fast IO, I got 1.74 s, 28 MB Last edit: 2019-06-23 19:44:20
	Alei Reyes: 2015-08-07 00:11:40 TLE in python, AC with PyPy
	Sahil Sharma: 2014-12-29 07:57:44 @ (Tjandra Satria Gunawan)(曾毅昆) really nice problem :) I got an AC but have a doubt, your python solution got an AC in about 1 s whereas mine too about 9 seconds. Could you please see why that is the case? Do I need to optimize the IO? Thanks
	shubham tiwari: 2014-11-24 20:49:17 I got the recursion in linear form.. but I am not able to implement it on c++. I was trying it with vectors but it doesn't work.. I am just one step behind with ac.. please help
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2014-03-04 18:25:43 @Min_25: case are generated randomly, if you want to help me to improve this problem, you can tell me that difficult case, and I'll add it when I have fast and stable internet connection (because the data is ~2MB)..
	Min_25: 2014-03-03 07:33:01 The most difficult case (in C++) does not seem to be included. EDIT: @Tjandra Satria Gunawan (曾毅昆) I think the most difficult case is m = 3^40 (=12157665459056928801). BigInteger (> 64 bit) class is required only in that case. Last edit: 2014-12-25 07:47:37
	[Lakshman]: 2013-07-05 10:40:56 @Tjandra Satria Gunawan)(曾毅昆) Can you please help me now I am getting correct output but getting TLE can you please tell me if I am doing something wrong??.. Last edit: 2013-08-09 11:47:02
	Aayush Tripathi: 2013-06-15 10:52:20 I'm getting two values for a(1). 2 and 7. On what basis should I ignore 7 as the answer is 2 ? --ans(francky)--> If you think a_1 = 7, then by definition a_0 = 42/16, and this is wrong. I don't (want to) know how you get 7 but it's a wrong answer. Good luck. --> Sorry i meant a(2). Last edit: 2013-06-15 13:33:06
	Gaurav Parida: 2013-05-26 11:59:26 Thanks... PS- Sorry, next time i will try to post such things in forums rather than here... Last edit: 2013-05-27 10:57:11

Submit solution!

Added by:	Tjandra Satria Gunawan
Date:	2013-03-14
Time limit:	13s
Source limit:	50000B
Memory limit:	1536MB
Cluster:	Cube (Intel G860)
Languages:	All except: ASM64
Resource:	ONMIPA sel 2013