GCD3  Discrete Math Problem
Given N, M and K (1 <= N, M <= 100^200 and 1 <= K <= 16) which
N = a + b
M = a^2 + b^2  (2^K  2) * a * b
with a > 0, b > 0 and gcd(a, b) = 1.
Your task is to find gcd(N, M).
Input
The input file consists of several data sets. The first line contains
the number of data sets T (1 <= T <= 10000). The fallowing T lines
describe the data sets, one triple (N, M, K) for each.
Output
For each data test in the input write the gcd(N, M).
Example
Input:
2
648570884104668119354133 420644191708310845403065233058235585438328857465 5
8017723549 59173349743176010825 9
Output:
1
1
Note: For the first trio a = 648570884104668119354126 and b = 7.
For the second a = 8016478423 and b = 1245126.
hide comments
y17prashant:
20181102 23:49:53
N and M are given as input so we can directly calculate gcd(N,M) ...So why its wrong i have checked for some cases on spoj toolkit it showing wrong answer . whats the use of k 

n_o_o_b_i_e:
20180614 15:48:35
The output only depends on N and K.


buttman:
20160703 12:06:12
Very strict memory limit. 

Ankit Jain:
20131209 14:52:15
Got to learn a lot from solving this problem....really nice one..:) 

Francky:
20130502 23:20:49
@Brian Curcio, you're right, I've edit the body of problem.


Brian Curcio:
20120429 03:31:01
In the first example, I think K should be 5, not 10, for M to be that number


Krunal:
20110318 16:52:43
No clue at all !!? 

Robert Gerbicz:
20091026 19:30:52
Have you rejudged all solutions? (It's quite curious that lot of 0.00 sec. AC time) 

Muhammad Ridowan:
20091025 16:50:20
The page is really wide. For the wide input. 

Brian Bi:
20091025 16:50:20
"Note: For the first trio a = 648570884104668119354126 y b = 7"

Added by:  Frank Rafael Arteaga 
Date:  20091024 
Time limit:  0.100s 
Source limit:  1000B 
Memory limit:  1536MB 
Cluster:  Cube (Intel G860) 
Languages:  ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS D ERL FORTRAN ICON ICK JSRHINO LUA NEM NICE OCAML PASGPC PASFPC PERL PRLGswi SCALA SCM qobi SCM guile ST TCL TEXT WHITESPACE 
Resource:  Discrete Math 