题目简介
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*104),b(1≤b≤109)。
样例输入
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;
}
}
}
