Problemi 023

Kërkesa

Çufoja ka një recetë me përbërësit që duhen për një gatim. Por sipas kësaj recete do të gatuhej shumë më tepër ushqim nga ç’i duhet Çufos. Kështu që ai do që ti pakësojë përbërësit, por duke ruajtur përpjesëtimin (raportin) e tyre, dhe duke qenë numra të plotë.

Reference: https://www.codechef.com/problems/RECIPE

Shembull

$ cat input.txt
3
2 4 4
3 2 3 4
4 3 15 9 6

$ python3 prog.py < input.txt
1 1
2 3 4
1 5 3 2

Për çdo rast testimi, numri i parë tregon numrin e përbërësve, dhe më pas vijnë sasitë përkatëse të përbërësve.

Zgjidhja 1

Sqarime

Për të zvogëluar vlerat e përbërësve duke ruajtur përpjesëtimet dhe duke qenë numra të plotë, duhet të gjejmë pjesëtuesin më të madh të përbashkët të të gjithë numrave, dhe ti pjesëtojmë me të. PMP të të gjithë numrave mund ta gjejmë duke përdorur këtë veti: \(pmp(a_1, a_2, a_3) = pmp(pmp(a_1, a_2), a_3)\)

Kemi përdorur gjithashtu edhe disa mjete të gjuhës Python që përdoren për listat. Bëni këto prova:

$ python3
>>> p = [0, 1, 2, 3, 4]
>>> p
[0, 1, 2, 3, 4]
>>> p[1:4]
[1, 2, 3]
>>> p[1:]
[1, 2, 3, 4]
>>> p[:-1]
[0, 1, 2, 3]
>>> p[-1]
4
>>> 

Detyra

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