HDU 5974 A Simple Math Problem 数学题

http://acm.hdu.edu.cn/showproblem.php?pid=5974

遇到数学题真的跪。。

题目要求

X + Y = a

lcm(X, Y) = b

设c = gcd(x, y);

那么可以表达出x和y了，就是x = i * c; y = j * c;

其中i和j是互质的。

所以lcm(x, y) = i * j * c = b

那么就得到两个方程了。

i * c + j * c = a;

i * j * c = b;

但是有一个c，三个未知数。

因为i和j互质，所以(i + j) 和 i * j 互质。

假设他们不互质，那么设那个数是x，有，i + j = m * x; i * j = k * x;

那么有i和j都能整除x，（由第一条可以得到了），这和i和j互质矛盾。

gcd(a, b) = c了，

然后就能解一个一元二次方程。有解的时候要输出最小解，因为这样确保不会一个取了较大的解，另一个变了负数。

#include <cstdio>

#include <cstdlib>

#include <cstring>

#include <cmath>

#include <algorithm>

#define IOS ios::sync_with_stdio(false)

using namespace std;

#define inf (0x3f3f3f3f)

typedef long long int LL;

#include <iostream>

#include <sstream>

#include <vector>

#include <set>

#include <map>

#include <queue>

#include <string>

LL a, b;

void work() {

    LL c = __gcd(a, b);

    LL B = a / c;

    LL C = b / c;

    LL diaota = B * B -  * C;

    LL t = inf / ;

    if (diaota >= )

        t = (LL)sqrt(diaota);

    LL ans1 = B + t;

    LL ans2 = B - t;

    if (diaota <  || t * t != diaota || ((ans1 & ) && (ans2 & ))) {

        cout << "No Solution" << endl;

    } else {

        LL x, y;

        if (ans1 %  ==  && ans2 %  == ) { //优先最小解

            LL tans = min(ans1, ans2);

            tans /= ;

            cout << tans * c << " " << (B - tans) * c << endl;

        } else if (ans1 & ) {

            ans2 /= ;

            x = ans2 * c;

            y = (B - ans2) * c;

            cout << ans2 * c << " " << (B - ans2) * c << endl;

        } else {

            ans1 /= ;

            x = ans1 * c;

            y = (B - ans1) * c;

            cout << ans1 * c << " " << (B - ans1) * c << endl;

        }

//        if (x + y != a) while (1);

    }

}

int main() {

#ifdef local

    freopen("data.txt","r",stdin);

#endif

    IOS;

    while (cin >> a >> b) work();

    return ;

}

巴特西

HDU 5974 A Simple Math Problem 数学题

最新文章

热门文章