HDU——5974 A SIMPLE MATH PROBLEM

题目简介

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
a(1≤a≤2*10^{4),b(1≤b≤10}9)。

样例输入

6 8
798 10780

样例输出

No Solution
308 490

题目分析

我借鉴别人的方法如下（可能叙述不好）：
1.记GCD(X,Y) = l。
2.记X = i×l , Y = j×l。
3.易知 i×l + j×l = a , i×j×l = b 。
4.因为i，j是两个互质的数，可证明他们的和与积互质。（这里不给出证明）
5.既然i+j和i×j互质了，那么GCD（a,b）= GCD(X,Y) = l。
6.既然l可求那么只用联立
i + j = a/l
i×j = b/l

#include<cstdio>
#include<cmath>
using namespace std;
#define LL long long

LL gcd(LL x,LL y)
{
    if(y==0) return x;
    else return(gcd(y,x%y));
}

int main()
{
    LL a,b;
    while(scanf("%lld%lld",&a,&b) != EOF)
    {
        LL l = gcd(a,b);
        LL n = b*l;
        LL det = a*a - 4*n;
        LL haha = sqrt(det);
        if(det < 0)
        {
            printf("No Solution\n");continue;
        }
        if(haha*haha == det && (a - haha)%2 == 0)
        {
            LL y = (a-haha)/2 ;
            LL x =  a - y;
            printf("%lld %lld\n",y,x);
        }
        else
        {
            printf("No Solution\n");continue;
        }

    }
}