HDU - 5974 - A Simple Math Problem 【数论】题解-蒲公英云

HDU - 5974 - A Simple Math Problem 【数论】题解

电玩女神 2021-07-25 00:18 464阅读 0赞

1.题目

Given two positive integers a and b,find suitable X and Y to meet the conditions:
X+Y=a
Least Common Multiple (X, Y) =b
Input
Input includes multiple sets of test data.Each test data occupies one line,including two positive integers a(1≤a≤2*104),b(1≤b≤109),and their meanings are shown in the description.Contains most of the 12W test cases.
Output
For each set of input data,output a line of two integers,representing X, Y.If you cannot find such X and Y,output one line of “No Solution”(without quotation).
Sample Input
6 8
798 10780
Sample Output
No Solution
308 490

2.代码

//c*i2-a*i+b=0
//a.b.c已知二元一次方程组求根 小的那个为i 大的为j
#include<iostream>
#include<cstdio>
#include<cmath> 
typedef long long ll;
using namespace std;
long long gcd(long long a,long long b)
{ 
    if(b==0)  return a;
    else return gcd(b,a%b);
}
int main()
{ 
   long long a,b;
   while(cin>>a>>b)
   { 
         ll c=gcd(a,b);
         ll d=a*a-4*c*b;
         if(d<0)
          { 
          cout<<"No Solution"<<endl;
          continue;
       }
         ll i=(a-sqrt(d))/2/c;
         ll j=a/c-i;
         ll x=i*c;
         ll y=j*c;
         if(x*y/c==b)
           cout<<x<<' '<<y<<endl;
         else
           cout<<"No Solution"<<endl;         
   }
   return 0;
}