Problemi 157

Kërkesa

Jepet një fushë me N rreshta (të numëruar nga 0 në N-1) dhe M shtylla (të numëruara nga 0 në M-1). Le ta shënojmë \((r, s)\) kutinë që ndodhet në rreshtin \(r\) dhe shtyllën \(s\).

Na jepet gjithashtu edhe një hap K, dhe kushti nqs ndodhemi në kutinë \((x, y)\) mund të lëvizim vetëm në njërën nga kutitë:

• \((x, (y + K) \% M)\)
• \(((x + K) \% N, y)\)
• \(((x + K) \% N, (y + K) \% M)\)

Një vizitë e plotë në fushë quhet një seri lëvizjesh të tilla që në çdo kuti të shkojmë të paktën një herë. Gjeni numrin më të vogël të kutive që mund të ndodhen në një vizitë të plotë. Ose nxirrni -1 nëse një vizitë e plotë nuk është e mundur.

Referenca: https://www.codechef.com/problems/GRIDTOUR

Shembull

$ cat input.txt
3
2 3 1
2 2 2
1 4 3

$ python3 prog.py < input.txt
6
-1
4

Jepen numrat N, M dhe K.

Shembulli 1: Një vizitë e mundshme është kjo: (0,1)→(1,2)→(0,0)→(1,0)→(1,1)→(0,2).

Shembulli 2: Nuk është e mundur një vizitë e plotë.

Shembulli 3: Një vizitë e mundshme është kjo: (0,2)→(0,1)→(0,0)→(0,3)

Zgjidhja

from math import gcd
for _ in range(int(input())):
    n, m, k = [int(i) for i in input().split()]
    print(n*m) if gcd(n,k)==1 and gcd(m,k)==1 else print(-1)