https://codeforces.com/contest/1525/problem/A
시간 1초, 메모리 256MB
input :
- t (1 ≤ t ≤ 100)
- k(1 ≤ k ≤ 100)
output :
- For each test case, print the minimum number of steps to brew a good potion. It can be proved that it's always possible to achieve it in a finite number of steps.
각 테스트 케이스에서 좋은 포션을 만들기 위한 최소한의 횟수를 출력하시오. 언제나 좋은 포션을 제작할 수 있습니다.
조건 :
-
The potion consists of two ingredients: magic essence and water. The potion you want to brew should contain exactly k % magic essence and (100−k) % water.
포션은 물과 마법 용액 두 가지로 구성되어 있습니다. 제작하려는 포션은 마법 용액 k%, 물 (100 - k)%로 이루어져 있습니다. -
In one step, you can pour either one liter of magic essence or one liter of water into the cauldron. What is the minimum number of steps to brew a potion?
한 번의 스텝으로 마법 용액을 1리터 혹은 물을 1리터 넣을 수 있습니다. 최소한의 횟수는 몇 번 입니까?
k가 실수가 아닌 정수이기 때문에 모든 농도는 1 : 99, 2 : 98 등으로 나타낼 수 있다.
이 때 문제에서 원하는 것은 최소한의 횟수를 물었으므로 위의 숫자들을 가장 작게 만들어야 한다.
즉, 두 수의 최대 공약수를 이용해서 숫자의 크기를 줄이고 이 둘을 합한다면 우리는 원하는 결과를 얻을 수 있다.
import sys
import math
t = int(sys.stdin.readline())
for i in range(t):
k = int(sys.stdin.readline())
num = math.gcd(k, 100 - k)
print(k // num + (100 - k) // num)
