AlgoSpot) POTION

문제 : https://algospot.com/judge/problem/read/POTION

마법의 약을 만드는데 넣어야할 재료의 최소량을 구하는 문제입니다.

유클리드알고리즘을 이용해서 마법의 약을 만드는데 필요한 재료들의 최소공배수를 찾은후 

가지고있는 모든 재료들중 가장 높은 비율로 나머지 재료들을 맞춰야합니다.

이떄 이 비율의 분모는 최소공배수여야합니다 왜냐하면 맞춰진 재료들이 정수여야하기때문입니다.

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

int n; // 재료의수

int recipe[200];
int cur[200];
int answer[200];

int gcd(int a, int b) {
	if (a < b) swap(a, b);
	return b == 0 ? a : gcd(b, a % b);
}

int upInt(int a, int b) {
	if (a % b == 0) return a / b;
	else return (a / b + 1);
}

void solve() {
	int b = recipe[0]; // 분모
	for (int i = 1; i < n; ++i) b = gcd(b, recipe[i]);
	
	int a = b; // 분자 
	for (int i = 0; i < n; ++i) a = max(a, upInt(cur[i] * b, recipe[i]));
	
	for (int i = 0; i < n; ++i) answer[i] = recipe[i] * a / b - cur[i];
}

int main() {
	std::ios::sync_with_stdio(false);

	int C;
	cin >> C;

	while (C--) {
		cin >> n;

		for (int i = 0; i < n; ++i) cin >> recipe[i];
		
		for (int i = 0; i < n; ++i) cin >> cur[i];
		
		solve();
		for (int i = 0; i < n; ++i) cout << answer[i] << " ";
		cout << endl;
	}
	return 0;
}