首页 > 代码库 > Solve Equation gcd(x,y)=gcd(x+y,lcm(x,y)) gcd(x,y)=1 => gcd(x*y,x+y)=1

Solve Equation gcd(x,y)=gcd(x+y,lcm(x,y)) gcd(x,y)=1 => gcd(x*y,x+y)=1

/**
题目:Solve Equation
链接:http://acm.hnust.edu.cn/JudgeOnline/problem.php?id=1643   //最终来源neu oj 2014新生选拔赛题
题意:给定两个数的和以及他们的最小公倍数,求这两个数。
思路:
x+y=A
lcm(x,y)=B => x*y/gcd(x,y)=B
要把这两个公式联立,那么必须消掉gcd;
设:d = gcd(x,y), x = kx*d, y = ky*d; kx与ky互质;

x+y=A => d(kx+ky)=A
x*y/gcd(x,y)=B => d*kx*ky=B

由于kx与ky互质,所以kx*ky与(kx+ky)互质,那么d的大小为gcd(A,B);

那么:
x+y=A
x*y/gcd(A,B)=B; 联立两个式子判断是否可以获得整数解再解方程即可。

得出结论:gcd(x,y) = gcd(A,B) = gcd(x+y,lcm(x,y));

一元二次方程解
b*b-4*a*c>=0有解。
x1 = (-b+sqrt(b*b-4*a*c))/(2*a);
x2 = (-b-sqrt(b*b-4*a*c))/(2*a);
要判断是否是整数解,则要对分母对分子取余为0,以及开根号后为整数值。
*/
#include<iostream>
#include<cstring>
#include<cstdio>
#include<algorithm>
#include<cmath>
using namespace std;
typedef long long ll;
const int maxn = 1000100;
ll gcd(ll a,ll b)
{
    return b==0?a:gcd(b,a%b);
}
int main()
{
    ll A, B;
    while(scanf("%lld%lld",&A,&B)==2)
    {
        ll d = gcd(A,B);
        ll deta = A*A-4*d*B;
        ll p = sqrt(deta+0.00001);
        if(p*p!=deta){
            printf("No answer\n");
        }else
        {
            if((A+p)%2!=0){
                printf("No answer\n");
            }else
            {
                ll x = (A-p)/2;
                ll y = (A+p)/2;
                printf("%lld %lld\n",x,y);
            }
        }
    }
    return 0;
}

 

Solve Equation gcd(x,y)=gcd(x+y,lcm(x,y)) gcd(x,y)=1 => gcd(x*y,x+y)=1