UVA 11889 Benefit(公约公倍)

#include <iostream>using namespace std;int gcd(int a,int b){return b==0?a:gcd(b,a%b);}int main(int argc, char *argv[]){long long a,L,t,i; cin>>t;while(t--){cin>>a>>L;if(L%a) cout<<"NO SOLUTION"<<endl;else{for(i=L/a;i<=L;i+=L/a){if(a/gcd(a,i)*i==L) { cout<<i<<endl;break;}}if(i>L) cout<<"NO SOLUTION"<<endl;}}return 0;}