Submit | All submissions | Best solutions | Back to list |
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 following 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.
Added by: | Frank Rafael Arteaga |
Date: | 2009-10-24 |
Time limit: | 0.100s |
Source limit: | 1000B |
Memory limit: | 1536MB |
Cluster: | Cube (Intel G860) |
Languages: | C CPP C99 |
Resource: | Discrete Math |