고동치는고동

문제 링크 : https://www.acmicpc.net/problem/3036 3036번: 링 문제 상근이는 창고에서 링 N개를 발견했다. 상근이는 각각의 링이 앞에 있는 링과 뒤에 있는 링과 접하도록 바닥에 내려놓았다. 상근이는 첫 번째 링을 돌리기 시작했고, 나머지 링도 같이 돌� www.acmicpc.net 사용 알고리즘 : GCD 서로 다른 톱니바퀴 A와 B가 맞물려 있을 때 A가 n톱니만큼 돌아가면 B도 n톱니 만큼 돌아가는 것은 당연한 사실이다. A가 a개 만큼의 톱니를 가지고 있고 B가 b개 만큼의 톱니를 가지고 있다고 한다면 A가 한바퀴 회전했을 때(a톱니 만큼 돌아갔을 때) B는 a/b 바퀴 만큼(a톱니 만큼) 돌아간다. 다음으로 구해진 모든 분수를 기약분수로 나타내면 된다. 이는 GC..

문제 링크 : https://www.acmicpc.net/problem/9613 9613번: GCD 합 문제 양의 정수 n개가 주어졌을 때, 가능한 모든 쌍의 GCD의 합을 구하는 프로그램을 작성하시오. 입력 첫째 줄에 테스트 케이스의 개수 t (1 ≤ t ≤ 100)이 주어진다. 각 테스트 케이스는 한 줄로 �� www.acmicpc.net 사용 알고리즘: gcd gcd 알고리즘만 알고 있다면 풀 수 있는 간단한 문제이다. 주의할 점은 gcd합이 int범위를 넘어갈 수 있기 때문에 long long으로 선언해줘야 한다는 것이다. 두 값이 모두 1,000,000일 경우 GCD도 1,000,000이 된다. 이러한 쌍이 최악의 경우 100*99/2개 만큼 존재할 수 있으므로 거뜬히 int범위를 벗어난다. 그..