BOJ-2942 퍼거슨과 사과

접근

1. 최대공약수
2. 약수 구하기

입력받은 두 수의 최대공약수를 구해준 후 최대공약수의 약수들을 구해주면 된다.
사과의 개수가 최대 10억 이므로 최대공약수를 구한 후 약수를 찾을 때 for문의 범위를 최대공약수의 제곱근까지 봐주면 최악 10억을 연산 횟수를 약 31622번 까지 줄일 수 있다.

#include <iostream>
#include <algorithm>
#include <vector>
using namespace std;
typedef long long ll;
vector<ll> v;
ll gcd(ll a, ll b) {
	if (b == 0) return a;
	return gcd(b, a % b);
}
int main() {
	ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
	ll a, g; cin >> a >> g;
	ll val = gcd(a, g);
	for (ll i = 1; i * i <= val; i++) {
		if (val % i == 0) {
			v.push_back(i);
			if (val / i == i) continue;
			v.push_back(val / i);
		}
		else continue;
	}
	sort(v.begin(), v.end());
	for (auto it : v) cout << it << " " << a / it << " " << g / it << "\n";
	return 0;
}