백준 BOJ 2942 - 퍼거슨과 사과

https://www.acmicpc.net/problem/2942

2942번: 퍼거슨과 사과

 

입력으로 들어오는 R과 G의 범위가 넓어서

for문으로 R,G 이하의 모든 수에 대해서 탐색하면

시간초과를 받게 될 수 있다.

 

시간을 절약하기 위해서 R과 G의 최대공약수를 찾아서

그 최대공약수의 약수를 찾는 방식으로 접근하면 조금 더 빠르게 풀 수 있다.

R과 G가 10억에 가까운 임의의 수 두개라면 이런경우에도 TLE가 나지 싶은데

테스트케이스가 그리 빡빡하지는 않은듯..?

 

#include <bits/stdc++.h>
using namespace std;

int gcd(int a, int b){
	if(b == 0) return a;
	return gcd(b, a%b);
}

int main(){
	int a,b;
	cin >> a >> b;
	
	int k = gcd(a,b);
	for(int i=1; i<=k; i++){
		if(a%i == 0 && b%i == 0){
			cout << i << " " << a/i << " " << b/i << "\n";
		}
	}
	return 0;
}