5618번: 공약수

문제접근🤔

• 입력 받을때 가장 큰 수를 업데이트 하고 1부터 그 큰수만큼 모든 입력 받은 숫자를 나눌 수 있는지 확인한다

놓쳤던 부분😅

• 유클리드 호제법으로 풀 수 있음

  #include <bits/stdc++.h>
  using namespace std;
  
  int n, a[3], _gcd;
  vector<int> ans;
  
  int gcd(int a, int b){
  	if(b == 0) return a;
  	return gcd(b, a%b);
  }
  
  int main() {
  	ios::sync_with_stdio(0);
  	cin.tie(0);
  
  	cin >> n;
  	for (int i = 0; i < n; i++) cin >> a[i];
  	
  	_gcd = gcd(a[0], a[1]);
  	if(n == 3) _gcd = gcd(_gcd, a[2]);
  
  	for (int i = 1; i*i <= _gcd; i++){
  		if(_gcd % i == 0){
  			ans.push_back(i);
  			if(_gcd/i != i) ans.push_back(_gcd/i);
  		}
  	}
  
  	sort(ans.begin(), ans.end());
  
  	for(auto x : ans) cout << x << '\\n';
  }
  
  

코드😁

2020 KB

328 ms

#include <iostream>
#include <vector>
using namespace std;

int main(void)
{
	int n;
	vector<int> v;
	int max = 0;
	bool flag = false;

	ios_base::sync_with_stdio(false);
	cin.tie(0);
	cout.tie(0);

	cin >> n;
	v.resize(n);

	for (int i = 0; i < n; i++)
	{
		cin >> v[i];
		if (v[i] > max)
			max = v[i];
	}
	for (int i = 1; i <= max; i++)
	{
		for (unsigned int j = 0; j < v.size(); j++)
		{
			if (v[j] % i != 0)
			{
				flag = true;
				break ;
			}
		}
		if (!flag)
			cout << i << "\\n";
		flag = false;
	}
	return (0);
}