T295392 獨幕喜劇的AMC第一章--2題解

這道題應該簡單吧，求最大公因數

思路：可以用輾轉相除，也可以用窮舉法（在程式裡，會變得很快）

首先介紹窮舉法

做法：從ab之間的最小數字枚舉到1。

我們可以這樣做：（python）

c=min([a,b])
while c:
    if a%c==0 and b%c==0:
        print(c)
        break
    c-=1
           

（c++）

for(long long i=a;i>0;i--)if(a%i==0 and b%i==0){s=i;break;}
           

當然，如果滿足條件，也可以替換成

for(long long i=a;i>0;i--)if(a%i==0 and b%i==0){cout<<s;return 0;}//直接傳回0，終止程式
           

這樣後面就不用再多寫傳回了。

完整程式

python

l=input().split(' ')#輸入以後去除空格，把兩邊的内容變成清單，注意這時候的清單還是字元串
a=int(l[0])#提取清單裡的資料并轉換成整數
b=int(l[1])
c=min([a,b])#提取最小數字
while c:
    if a%c==0 and b%c==0:
        print(c)
        break
    c-=1
           

c++

#include<iostream>
using namespace std;
int main(){
    long long a,b,s;
    cin>>a>>b;
    for(long long i=a;i>0;i--)if(a%i==0 and b%i==0){s=i;break;
	}
    cout<<s;
    return 0;
}