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).
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.
For each data test in the input write the gcd(N, M).
648570884104668119354133 420644191708310845403065233058235585438328857465 5
8017723549 59173349743176010825 9
Note: For the first trio a = 648570884104668119354126 and b = 7.
For the second a = 8016478423 and b = 1245126.
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
The output only depends on N and K.
Very strict memory limit.
Got to learn a lot from solving this problem....really nice one..:)
@Brian Curcio, you're right, I've edit the body of problem.
In the first example, I think K should be 5, not 10, for M to be that number
No clue at all !!?
Have you rejudged all solutions? (It's quite curious that lot of 0.00 sec. AC time)
The page is really wide. For the wide input.
"Note: For the first trio a = 648570884104668119354126 y b = 7"
|Added by:||Frank Rafael Arteaga|
|Cluster:||Cube (Intel G860)|
|Languages:||ADA95 ASM32 BASH BF C CSHARP CPP C99 CLPS D ERL FORTRAN ICON ICK JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PRLG-swi SCALA SCM qobi SCM guile ST TCL TEXT WHITESPACE|