请问最少要拾取多少子弹到背包,才能使得背包里的子弹数恰好是x的倍数又恰好是y的
倍数。
一句话题意:读入x,y,求x,y的最小公倍数
求出x与y的最小公约数(gcd),然后用x*y除以gcd(x,y)
需要注意的是这题要开long long……
C++虽然有个gcd函数不过我还是自己写了个(
代码如下:
#include<iostream> #include<math.h> #include<algorithm> #include<stdio.h> #include<string.h> #define int long long using namespace std; int T,x,y; inline int read() { int n=0,f=1; char c=getchar(); while(c<'0'||c>'9') {if(c=='-') f=-1; c=getchar();} while(c>='0' && c<='9') {n=n*10+c-'0'; c=getchar();} return n*f; } inline int gcd(int x,int y) {return y==0?x:gcd(y,x%y);} signed main(void) { T=read(); for(int i=1; i<=T; i++) { x=read(); y=read(); int g=gcd(x,y); cout<<"Case "<<i<<": "<<x/g*y<<'\n'; } return 0; }