SPOJ.com - Problem GCD3

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.

Submit solution!

hide comments

< Previous 1 2 Next >

	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 (2K-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)

Submit solution!

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