[백준] 5618번 - 공약수 (C++) 문제 및 풀이

문제) 백준 - 수학 - 공약수

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

5618번: 공약수

 

숫자들의 모든 공약수를 구하는 문제였습니다. 모든 숫자들에 대해 최대 공약수를 구하여 그 최대 공약수의 약수들을 출력하면 해결할 수 있습니다.

 

C++ 소스코드)

	#include<bits/stdc++.h>
	#define ll long long
	#define INF 987654321
	#define MAX 4002
	using namespace std;
	typedef pair<int, double> p;
	int N;
	int arr[MAX];
	int solve(int a, int b){
	if(a > b) swap(a, b);
	if(b % a == 0) return a;
	return solve(b % a, a);
	}
	int main() {
	ios_base::sync_with_stdio(0);
	cin.tie(0); cout.tie(0);
	cin >> N;
	for(int i = 0; i < N; ++i)
	cin >> arr[i];
	int gcd = arr[0];
	for(int i = 1; i < N; ++i)
	gcd = solve(gcd, arr[i]);
	for(int i = 1; i <= gcd; i++)
	if(gcd % i == 0)
	cout << i << endl;
	return 0;
	}

view raw 5618.cpp hosted with ❤ by GitHub