D - A Simple Math Problem 解题报告

题目链接：https://vjudge.net/contest/381753#problem/D
解题思路：
跟据题意可以列出两个式子：
X+Y=a （1）
LCM(X,Y)=b （2）
题目让求X,Y，我们思考如何把（2）做一个转化变为一个一般方程

使用结论：gcd(X,Y)=gcd(X+Y,Y)=gcd(X,X+Y)=gcd(X+Y,lcm(X,Y))
证明gcd(X,Y)=gcd(X+Y,lcm(X,Y))
设：X=r1k,Y=r2k,(r1,r2互质，k是gcd(X,Y))
lcm(X,Y)=r1r2k
X+Y=(r1+r2)*k
因为r1与r2互质，r1,r2都与(r1+r2)互质，所以得证。

LCM(X,Y)=XY/gcd(X,Y)=XY/gcd(X+Y,LCM(X,Y))=X*Y/gcd(a,b)

X+Y=a
XY=bgcd(a,b)
求解这个方程便可得答案。

代码：

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
ll gcd(ll a, ll b)
{
    return b ? gcd(b, a%b) : a;
}
int main()
{
    ll a, b;
    while(scanf("%lld%lld",&a,&b)!=EOF)
    {
        bool flag = 1;
        ll k1, k2;
        ll g = gcd(a,b);
        ll deta = a*a - 4*b*g;
        if(deta < 0) {
            flag = 0;
        }
        ll aa = sqrt(deta);    //过滤掉答案是小数的情况的方法就是看sqrt*sqrt取整后是否与原来相同 
        if(aa*aa == deta)
        {
            if((a+aa)%2!=0||(a-aa)%2!=0||(a-aa)<=0||(a+aa)<=0)
            {
                flag = 0;
            }
            else
            {
                k1 = (a+aa)/2;
                k2 = (a-aa)/2;
            }
        }
        else flag = 0;
        if(flag) {
            printf("%lld %lld\n",min(k1,k2),max(k1,k2));
        }
        else
            printf("No Solution\n");
    }
}