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 >

	Federico LebrÃ³n: 2013-05-06 03:50:37 I liked this problem, thank you :)
	Ivan Hendrajaya: 2013-05-04 20:42:04 @Tjandra: Thanks, take a long time for me to solve this problem. For now C++ is my main programming language, so I try to solve this problem with highly (not fully) optimized C++ code. I think it would be better if the number of test cases is not that much. :)
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-04-28 10:17:35 @Ivan Hendrajaya: wow! superb solution... heavily optimized code written in C family ;-) I've been waiting that for a long time, finally it come.. thanks and congratulations, I hope you enjoy this problem.. :-D Last edit: 2013-04-28 11:09:18
	Andy: 2013-04-17 20:21:00 why am I getting NZEC? --ans(francky)--> It seems most of recent NZEC are in fact TLE... --(andy) Yeah, I noticed that after looking for a while in judge status... Anyway, got AC with C and without biginteger, use overflow manipulation :) Ans(Tjandra): wow, you did it without bignum, without fast I/O, and using order 3 formula (the optimal formula is in order 1). I think your "overflow manipulation" has a big chance to become the fastest one ;-) Last edit: 2013-04-17 22:29:43
	Shubham Depp Bansal: 2013-03-23 06:22:05 recursion limit is too much in python. why? --ans(francky)--> A well designed algo should not have such a problem ; the max depth is 64, and the default limit for python is 100000. You have to find a better formula, I think. Done..Just too much mathematics :) Last edit: 2013-03-25 11:22:26
	Michael Kharitonov: 2013-03-22 16:43:30 Insidious author chose the bounds of m to make C solution more complicated. Last edit: 2013-03-22 20:23:06
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-03-19 16:14:53 seems that I pass that ONMIPA selection test 2013 (university level) :-D so start from tomorrow (20 March 2013) I'll be unavailable on SPOJ due to preparation on Regional Math Olympiad (ONMIPA regional level) until 11 April 2013, Sorry for inconvenience. Last edit: 2013-03-19 18:14:07
	(Tjandra Satria Gunawan)(æ›¾æ¯…æ˜†): 2013-03-16 09:13:34 You can challenge yourself to solve this problem using C language, if you feel you solve this problem easily :-) Just info: My 4KB of C code AC under 10s, and need ~6 hours for me to debug that long code...
	Nipun Poddar: 2013-03-15 11:57:19 thanks Last edit: 2013-03-15 14:59:28
	Francky: 2013-03-15 08:45:52 Cool, 120B of python code. Ans(Tjandra): My python 3 code was 123B (initial) now golfed to 99B ;-) Also we use different formula, my formula seems a bit slower but let me easy to golf :-) And congratulations, you're the fastest for now :-D Last edit: 2013-03-15 21:53:57

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