【題目敘述】https://zerojudge.tw/ShowProblem?problemid=e520
【解題想法】
- 想找出每種藥物服用時間的最小公因數，當成時間累進的最小單位。
- 時間刻度每前進一格，就檢查每一種藥物是否該服用，直到滿足須服用的最少藥物數量。
#include <iostream>
using namespace std;
int myGCD(int x, int y){
while ((x%=y) && (y%=x));
return x+y;
}
int main() {
int T, n, k;
cin >> T;
while (T--){
cin >> n >> k;
string m[n];
int f[n];
for (int i = 0; i < n; i++){
cin >> m[i] >> f[i];
}
int D = f[0];
for (int i = 1; i < n; i++){
D = myGCD(D, f[i]);
}
int Time = D, cnt = 0;
while (cnt < k){
for (int i = 0; i < n && cnt < k; i++){
if (Time % f[i] == 0){
cout << Time << " " << m[i] << "\n";
cnt++;
}
}
Time += D;
}
}
return 0;
}