[POTION] 마법의 약

• 분류: 정수론
  
• 난이도: 중
• 입력: 테스트 케이스 C, 재료의 수 N(1<=N<=200), 약에 들어가야 하는 각 재료의 양 Ri, 이미 냄비에 넣은 재료의 양 Pi(1<=Ri, Pi<=1000)
• 출력: N개의 정수로 각 재료마다 더 넣어야 하는 양 출력(단, 최소 한병은 나와야 한다.)
• 소스

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

int recipe[200], put[200], remain[200];
int GCD(int);
int gcd(int, int);
int ceil(int, int);
void potion(int);

int main(){
	int C;
	cin >> C;
	for (int testcase = 1; testcase <= C; testcase++){
		int number;
		cin >> number;
		for (int i = 0; i < number; i++) cin >> recipe[i];
		for (int i = 0; i < number; i++) cin >> put[i];

		potion(number);
		for (int i = 0; i < number; i++) cout << remain[i] << " ";
		cout << endl;
	}
	return 0;
}

void potion(int n){
	int gcd = GCD(n), mul = gcd;
	for (int i = 0; i < n; i++){
		mul = max(mul, ceil(put[i] * gcd, recipe[i]));
		recipe[i] /= gcd;
	}

	for (int i = 0; i < n; i++) remain[i] = recipe[i] * mul - put[i];
}

int ceil(int a, int b){
	return (a + b - 1) / b;
}

int GCD(int n){
	int ret = recipe[0];
	for (int i = 1; i < n; i++)
		ret = gcd(ret, recipe[i]);
	return ret;
}

int gcd(int a, int b){
	if (b == 0) return a;
	else return gcd(b, a % b);
}

• 소스 설명: 

1. int gcd(int a, int b): 파라미터 a, b의 최대 공약수를 구한다.
2. int GCD(int n): 주어진 n개의 입력(recipe)의 최대 공약수를 구한다.
3. int ceil(int a, int b): a/b와 같거나 큰  최소의 정수를 구한다.
4. int potion(int n): 주어진 n개의 재료의 넣어야 하는 양을 구한다. 처음 모든 재료의 최대 공약수를 구하고, ceil을 호출해 최소의 정수를 곱한다. 그리고 remain[i]에 recipe[i] * mul / gcd - put[i]를 구한다.

• 참고 사이트: https://algospot.com/judge/problem/read/POTION