UVa 11889 - Benefit

b一定为c/a的倍数,lcm=ab/gcd,lcmgcd=a*b。然后枚举。

PS:一开始忽略了相乘会爆掉int这个问题。。WA了两次。。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
#include<iostream>
#include<algorithm>
using namespace std;
int gcd(int a,int b) {
return (b?gcd(b,a%b):a);
}
int main(){
int n;
cin>>n;
while(n--){
int a,c;
cin>>a>>c;
if(c%a){
cout<<"NO SOLUTION"<<endl;
continue;
}
int t=c/a;
for(int b=t;b<=c;b+=t){
long long i=(long long)c*gcd(a,b),j=(long long)a*b;
if(i==j){
cout<<b<<endl;
break;
}
}
}
return 0;
}

** 本文迁移自我的CSDN博客,格式可能有所偏差。 **