105學年度彰雲嘉區資訊能力競賽複賽程式設計題Q4(長方形的切割)

一個長寬皆為整數的長方形可以切割成數個相同大小的整數邊長正方形，例如下圖中，一個長12公分、寬6公分的長方形可以切割成72個邊長為1公分的正方形、18個邊長為2公分的正方形、8個邊長為3公分的正方形、或2個邊長為6公分的正方形。本題請輸入長方形的長和寬(單位公分，皆為整數，中間以空格隔開)，輸出可以切割成哪幾種整數邊長的正方形，以及這些相同大小正方形的個數各有多少個(可切割之整數邊長正方形的邊長與個數，以空格隔開，依據邊長由小到大之順序逐行列出)。

輸入說明 ：

輸入長方形的整數長和整數寬

輸出說明 ：

輸出可切割之整數邊長正方形的邊長與個數(以空格隔開，依邊長由小到大之順序)

範例1輸入：
12 6

範例1輸出：

1 72

2 18

3 8

6 2

Python code：

def gcd(m, n): # 找長與寬的最大公因數
    return m if n == 0 else gcd(n, m % n)
m,n=input().split()
m,n=int(m),int(n)
a=gcd(m,n) #取出長寬的最大公因數
x=[]
 #將最大公因數的因數存在a中
for i in range(1,a+1):
    if (a%i)==0:
        x.append(i)
for k in range(len(x)):
    b=int(m*n/x[k]/x[k]) #b為面積除以小正方形面積，即個數
    print(x[k],b)