백준 3036 - 링(C++)

문제 링크입니다. https://www.acmicpc.net/problem/3036

3036번: 링

유클리드 호제법을 이용한 문제입니다.

첫번째 링의 길이를 기준으로 다른 링들과의 최대 공약수를 구해줍니다. -> 이때 유클리ㄷ, 호제법이 이용됩니다.

최대 공약수를 구해줬다면, 값을 바탕으로 링이 도는 횟수를 출력해주면 됩니다.


자세한 것은 코드를 참고해주세요.

#define _CRT_SECURE_NO_WARNINGS
#include <iostream>

using namespace std;

int N;
int ring[101];

int Ucild(int x, int y){
	int num = x, div = y;
	while(1){
		if(div == 0) return num;
		int t = num;
		num = div;
		div = t % div;
	}
}

int main(){
	cin.tie(0);
	cout.tie(0);
	cin >> N;
	for(int i = 1; i <= N; i++){
		cin >> ring[i];
	}	
	for(int i = 2; i <= N; i++){
		int div = Ucild(ring[1], ring[i]);
		cout << ring[1] / div << "/" << ring[i]/div << "\n";
	}
	return 0;
}

질문 및 조언은 코드를 참고해주세요.