HDU5974 A Simple Math Problem---数论--转化解方程

感谢:http://blog.csdn.net/mirror58229/article/details/63685884

题意：x+y=a lcm(x,y)=b 求x,y

12WCases + b 10^9 + a 10^4

所以肯定不是枚举……肯定是公式题

接下来就是转化

x+y=a

x*y/gcd(x,y)=b

令gcd(x,y)=c

x=i*c,y=j*c

i*c+j*c=a

c*i*j=b

c*(i+j)=a

c*i*j=b

因为i j互质所以gcd(a,b)=c=gcd(x,y) 【最重要的条件】

所以一开始就能得到c值，剩下就是求根

i+j=a/c

i*j=b/c

i+b/(c*i)=a/c

c*i²-a*i+b=0

a.b.c已知二元一次方程组求根小的那个为i 大的为j

最后因为求根时整除可能会出现小数，这是不满足题意的，丢掉这种情况即可

#include <iostream>

#include <cstdio>

#include <cstring>

#include <cmath>

#include <algorithm>

using namespace std;

typedef long long ll;

ll gcd(ll a,ll b)

{

    return b==?a:gcd(b,a%b);

}

int main()

{

    ll a,b;

    while(scanf("%lld%lld",&a,&b)!=EOF)

    {

        ll c=gcd(a,b);

        ll d=a*a-*b*c;

        if(d<)

        {

            printf("No Solution\n");

            continue;

        }

        ll i=(a-sqrt(d))//c;

        ll j=a/c-i;

        ll x=c*i;

        ll y=c*j;

        if(x*y/c==b)

            printf("%lld %lld\n",x,y);

        else

            printf("No Solution\n");

    }

}

巴特西

HDU5974 A Simple Math Problem---数论--转化解方程

最新文章

热门文章