UVa 11889 - Benefit

发表于 分类于 ， ， Disqus：

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博客，格式可能有所偏差。 **