绝地求生(pubg)

题目

求最少要拾取多少个子弹到背包中，使得背包里的子弹个数恰好是 x 的倍数且是 y 的倍数。

解题思路

求 x 和 y 的最小公倍数。
先求 x 和 y 的最大公因数 k = __gcd(x,y)，则最小公倍数为 x * y / k。

C++代码

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

typedef unsigned long long ULL;

int main(){
    int t;
    cin >> t;
    ULL x, y;
    for(int i=1; i<=t; ++i){
        cin >> x >> y;
        ULL k = __gcd(x,y);
        ULL ans = x / k * y;
        cout << "Case " << i << ": " << ans << endl;
    }
    return 0;
}