Problemi 110

Kërkesa

Një fermer do të shesë tokën e tij, e cila është në formë drejtkëndëshi me përmasa M dhe N. Meqenëse copat e tokës në formë katrore kanë çmim më të lartë, ai do që ta ndajë tokën e tij në copa katrore të barabarta. Sa është numri më i vogël i katrorëve të barabartë që mund të krijohen në tokën e tij?

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

Shembull

$ cat input.txt
2
10 15
4 6

$ python3 prog.py < input.txt
6
6

Zgjidhja

import math
for _ in range(int(input())):
    m, n = map(int, input().split())
    d = math.gcd(m, n)
    print((m // d) * (n // d))

Sqarime

Duhet të gjemë pjesëtuesin më të madh të përbashkët të dy brinjëve të drejtkëndëshit, dhe pastaj ta ndajmë secilën brinjë sipas tij.