UVA 11889 - Benefit-白红宇

UVA 11889 - Benefit

阅读量：6263 次

发布时间：2019-06-22

本文共 1573 字，大约阅读时间需要 5 分钟。

Benefit

Recently Yaghoub is playing a new trick to sell some more. When somebody gives him A Tomans, he who never has appropriate changes, asks for B Tomans such that lowest common multiple of A and B equals to C and he will pay back a round bill. Or otherwise take some snack instead of the remaining of his money. He believes that finding such a number is hard enough that dissuades students from paying that.

You should write a program that help poor students giving the appropriate amount of money to Yaghoub. Of course if there are several answers you go for students' benefit which is the lowest of them.

Input

The first line begin with an integer T ( T $\le$ 100000 ), the number of tests. Each test that comes in a separate line contains two integers A and C ( 1 $\le$ A, C $\le$ 10⁷ ).

Output

Print the lowest integer B such that LCM(A, B) = C in a single line. If no such integer exists, print " NO SOLUTION " instead. (Quotes for clarity)

Sample Input

32 632 17607 16

Sample Output

355NO SOLUTION

题目大意：三个数关系 lcm(a,b)=c,已知a和c,求最小的b，没有输出-1

解题思路：b为c的约数，枚举b 满足gcd(a,b)*lcm(a,b)==a*b这个条件即可，但是注意乘法用 long long

#include 
    
     #include 
     
      #include 
      
       #include 
       
        #include 
        
         using namespace std;int gcd(int a,int b){	return (b>0)?gcd(b,a%b):a;}int getb(int a,int c){	if(c

v; int max0=int( sqrt(c*1.0)+0.1 ); for(int i=1;i<=max0;i++){ if(c%i==0){ v.push_back(i); v.push_back(c/i); } } sort(v.begin(),v.end()); for(int i=0;i

0){ scanf("%d%d",&a,&c); int b=getb(a,c); if(b==-1) printf("NO SOLUTION\n"); else printf("%d\n",b); } return 0;}

转载地址：http://dazpa.baihongyu.com/

你可能感兴趣的文章