HDU5974 A Simple Math Problem(真~

这题大致意思是给两个数字a, b, 让你求出x, y满足

1、X+Y=a

2、LCM(X, Y) = b; 即X, Y的最小公倍数为b

由两个条件可以推导出公式

x1= (X + sqrt(XX - 4ygcd(x,y) ) ) /2;

y1 = X - x1;

可以用代码模拟解方程的过程

#include <stdio.h>
#include <math.h>
#include <stdlib.h>
#include <string.h>
#include <algorithm>
using namespace std;

long long gcd(long long x, long long y)
{
    return y==0 ? x : gcd(y, x%y);
}

int main()
{
    long long n, m, d, x1, y1, ans, dx, x, y;
    while(scanf("%lld%lld", &x, &y)!=EOF)
    {
        long long d = gcd(x,y);
        if((x*x - 4*y*d)<0) //Δx<0时，方程无解
        {
            printf("No Solution\n");
            continue;
        }
        else
        {
            x1= (x + sqrt(x*x-4*y*d))/2;   //√(x*x-4*y*d)  很明显的方程过程
            y1 = x - x1;
            if(y1 + x1 == x && y1*x1/gcd(y1,x1) == y)
            {
                printf("%lld %lld\n",y1, x1);
            }
            else
                printf("No Solution\n");
        }

    }
    return 0;
}

其实这题推导方法很多，例如韦达定理之类
完全分解开如下

#include <iostream>
#include <string.h>
#include <algorithm>
#include <stdio.h>
#include <math.h>
using namespace std;

int gcd(int x, int y)
{
    return y ? gcd(y ,x%y) : x;
}

int main()
{
    int a, b;
    while(scanf("%d %d",&a,&b)!=EOF)
    {
        int ans = gcd(a, b);
        a /= ans;  //可以算约分
        b /= ans;
        int d = a*a - 4*b; //Δx
        if(d < 0)
            puts("No Solution");
        else
        {
            int dx = sqrt(d); //√Δx
            if(dx*dx != d) //√Δx 无整数解，排除
                printf("No Solution");
            else
            {
                if((a-dx)%2!=0 || (a+dx)%2!=0) //两根非整数，排除
                    Δ("No Solution");
                else
                {
                    int x1 = (a - dx) / 2 * ans;  //x1
                    int x2 = (a + dx) / 2 * ans;  //x2
                    if(x1>0 && x2>0) //若小于0， 不符合，排除
                    {
                        if(x1 > x2) //将 小根 放在前面
                        {
                            int temp = x1;
                            x1 = x2;
                            x2 = temp;
                        }
                        printf("%d %d\n", x1, x2);
                    }
                }
            }
        }
    }
    return 0;
}