GCD4 - Discrete Math Problem (shorten)

Warning: This problem looks like, but differs from GCD3 :
GCD3 : (2K-2) ---vs--- GCD4 : (2K-2)
Moreover, your challenge will be to shorten your code to get more points.
GCD4 could be harder than GCD3!

Input

The first line of input contains an integer T, the number of test cases.
On each of the next T lines, your are given three integers N, M and K such that:
N = a + b
M = a2 + b2 - (2K-2)×a×b
with a > 0, b > 0 and gcd(a, b) = 1.

Output

For each test case, you have to print gcd(N, M), the greatest common divisor.

Example

Input:
2
2214811 1451126169481 7
107603 9066347749 9

Output:
1
1

Note: For the first trio a = 117651 and b = 2097160.
For the second a = 1313 and b = 106290.

Constraints

0 < T < 14321
0 < N < 10^200
1 < M < 10^200
0 < K < 17

For your information, my 293B C code get AC in 0.03s with 1.6MB of memory print.
Size code limit will be 666B.
Language restrictions are quite the same than in GCD3, and it is justified ;-)
Have fun ;-)


Added by:Francky
Date:2013-05-03
Time limit:1s
Source limit:666B
Memory limit:1536MB
Cluster: Cube (Intel G860)
Languages:C-CLANG C C++ 4.3.2 CPP CPP14 CPP14-CLANG C99 D-CLANG D FORTRAN PAS-GPC PAS-FPC
Resource:GCD3

hide comments
2017-02-12 01:51:36 Francky
Some languages were added. Ask for Rust or Dart, or ??? If need, as long as there's no integrated bignum library.
2014-06-21 03:23:36 Linghui Liu
@mitchs, thanks very much.
2014-06-21 00:32:53 Mitch Schwartz
@Linghui Liu: Congrats! For this and the other numerous records you've recently taken. :p
2013-11-23 03:59:48 Linghui Liu
@Mitch Schwartz Sorry for the spoiler, thanks for the comment. I still can't get the first case AC, but I use the same function.

Eventually, found the logical mistake for the first case by generating some test set.

EDIT: 113 now :p

Last edit: 2014-05-28 14:16:38
2013-11-21 05:41:39 Mitch Schwartz
@Linghui Liu: I've hidden your comment because of spoilers. It is still visible to Francky and some others. Regarding your question, you must have some bug in the first case, and in the second case you've made a math error. (You could easily find a counterexample by randomly generating some cases.)
2014-04-29 22:05:56 (Tjandra Satria Gunawan)(曾毅昆)
@Michael Kharitonov: If K is arround 10^200, then K will be useless information. better to compute gcd(M,N) directly. (Correct Me If I'm Wrong)
--ans(francky)--> Kind of a spoil, so I must hide this comment.
Edit(Tjandra): I think other user will not get a clue from this comment. I still say that this information is not spoil. But it's ok, this comments is stay hidden, you can delete it if you want.

Last edit: 2013-05-12 10:01:09
2013-05-11 20:31:51 Michael Kharitonov


Last edit: 2013-05-14 20:30:38
2013-05-11 10:39:03 (Tjandra Satria Gunawan)(曾毅昆)
easy points, thanks :-)
2013-05-05 05:50:33 Aditya Pande
i just don't get what Mitch is doing? incredible...:)
--ans--> You both are incredible ;-)

Last edit: 2013-05-05 08:15:42
© Spoj.com. All Rights Reserved. Spoj uses Sphere Engine™ © by Sphere Research Labs.