發表新討論
#13679: 請問TLE要怎麼解決


lawrence890815@gmail.com (智濬李)

a738. 最大公约数 -- 海豚原创 | From: [36.229.219.233] | 發表日期: 2018-04-06 20:17 
#include<iostream>
#include<math.h>


using namespace std;
int main(){
	int a,b,c,d;
	while(cin>>a>>b){

	if(a==b){
		cout<<a<<endl;
	}
	if(a>b){
		c=a;
		for(int i=1;i<=b;i++){
		if(a%i==0 && b%i==0){
			a=a/i;
			b=b/i;
			if(i!=1) i=i-1;
		}
		}
		cout<<c/a<<endl;
	}
	if(b>a){
		c=a;
		for(int i=1;i<=a;i++){
		if(a%i==0 && b%i==0){
			a=a/i;
			b=b/i;
			if(i!=1) i=i-1;
		}
		}
		cout<<c/a<<endl;
	}
	}
	
	
	}
#13680: Re:請問TLE要怎麼解決


asnewchien@gmail.com (david)

a738. 最大公约数 -- 海豚原创 | From: [36.232.33.157] | 發表日期: 2018-04-06 20:53 
#include
#include


using namespace std;
int main(){
	int a,b,c,d;
	while(cin>>a>>b){

	if(a==b){
		cout<<a<<endl;
	}
	if(a>b){
		c=a;
		for(int i=1;i<=b;i++){
		if(a%i==0 && b%i==0){
			a=a/i;
			b=b/i;
			if(i!=1) i=i-1;
		}
		}
		cout<<c/a<<endl;
	}
	if(b>a){
		c=a;
		for(int i=1;i<=a;i++){
		if(a%i==0 && b%i==0){
			a=a/i;
			b=b/i;
			if(i!=1) i=i-1;
		}
		}
		cout<<c/a<<endl;
	}
	}
	
	
	}


gcd 有比較快的算法，可參考提示。

ZeroJudge Forum