GCD3 - Discrete Math Problem

no tags 

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.


hide comments
smso: 2022-11-29 05:46:06

Find patterns by solving small coprimes of a and b with different K's by brute force. M is not needed. Source limit of 1000 bytes suggests a simple answer.

David: 2021-08-12 17:44:10

How about opening to the Java language?

y17prashant: 2018-11-02 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: 2018-06-14 15:48:35

The output only depends on N and K.

buttman: 2016-07-03 12:06:12

Very strict memory limit.

Ankit Jain: 2013-12-09 14:52:15

Got to learn a lot from solving this problem....really nice one..:)

Francky: 2013-05-02 23:20:49

@Brian Curcio, you're right, I've edit the body of problem.
By the way I remark that I solved luckily this problem : I solved (2*K-2) instead of (2^K-2) and my solution got AC, hahaha.
====
The 0.00s solutions seems curious : are they rejudged with the "Refresh cached info about test sequence" checked ? I don't think so, and only the first small input file was taken into account. I think it's possible those submissions need to be rejudged. @psetter : can you check that as Robert Gerbicz ask it too ?
====
Moreover, it seems that at least the first file have its last line without '\n', is it voluntarily ?

==edit: I've send a mail to author.
(edit) 0.00s rejudged, many thanks.

Last edit: 2013-05-03 12:50:38
Brian Curcio: 2012-04-29 03:31:01

In the first example, I think K should be 5, not 10, for M to be that number

Krunal: 2011-03-18 16:52:43

No clue at all !!?

Robert Gerbicz: 2009-10-26 19:30:52

Have you rejudged all solutions? (It's quite curious that lot of 0.00 sec. AC time)


Added by:Frank Rafael Arteaga
Date:2009-10-24
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 JS-RHINO LUA NEM NICE OCAML PAS-GPC PAS-FPC PERL PRLG-swi SCALA SCM guile SCM qobi ST TCL TEXT WHITESPACE
Resource:Discrete Math