https://www.acmicpc.net/problem/2942
시간 1초, 메모리 128MB
input :
- R G(1 ≤ R, G ≤ 1,000,000,000)
output :
- 사과를 받게되는 선수의 수 N과 나누어 주는 빨간 사과의 수 X와 초록 사과의 수 Y를 출력
최대 공약수를 구하고.
공약수의 약수를 이용해서 r, g를 나눈 값들을 출력해주어야 한다.
최대 공약수를 gcd를 통해서 구하고, 에라토스테네스의 체 쓰는 것처럼 해서. 로 공약수의 약수를 구하자.
import sys
from math import sqrt
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
r, g = map(int, sys.stdin.readline().split())
factor = gcd(r, g)
factor_list = set()
for i in range(1, int(sqrt(factor) + 1)):
if factor % i == 0:
factor_list.add(i)
factor_list.add(factor // i)
for item in factor_list:
print(item, r // item, g // item)
