發表新討論
#15858: 為甚麼會 killed


d10732114@gapps.fg.tp.edu.tw (d10732114)

學校 : 臺北市立第一女子高級中學
編號 : 86906
來源 : [203.64.52.24]
最後登入時間 ：
2018-11-06 10:09:30
a738. 最大公约数 -- 海豚原创 | From: [27.147.40.102] | 發表日期 : 2018-11-04 07:33

#include <iostream>
using namespace std;

int main()
{
long long int n,m,a;
while (cin>>n>>m)
{
for (int i=1; i<=m&&i<=n; i++)
{
if(n%i==0&&m%i==0)
a=i;
}

if(n==0&&m==0)
break;

cout <<a<< endl;
}

}

 
#15863: Re:為甚麼會 killed


rollfc (胖胖貓)

學校 : 國立清華大學
編號 : 81012
來源 : [36.229.40.133]
最後登入時間 ：
2024-05-19 16:21:40
a738. 最大公约数 -- 海豚原创 | From: [140.113.208.181] | 發表日期 : 2018-11-04 10:28

#include
using namespace std;

int main()
{
long long int n,m,a;
while (cin>>n>>m)
{
for (int i=1; i<=m&&i<=n; i++)
{
if(n%i==0&&m%i==0)
a=i;
}

if(n==0&&m==0)
break;

cout <<a<< endl;
}

}

你的作法是從1開始找到 min(m,n) 之間找到可以被m和n整除的數字

但是當m=n=1000000000時搜尋範圍過大，顯然這個方法會超時

請使用輾轉相除法來處理這個問題

 
ZeroJudge Forum