美文网首页
A Simple Math Problem

A Simple Math Problem

作者: 散落的魔王 | 来源:发表于2017-01-15 01:17 被阅读0次

Given two positive integers a and b,find suitable X and Y to meet the conditions:
X+Y=a
Least Common Multiple (X, Y) =b
Input
Input includes multiple sets of test data.Each test data occupies one line,including two positive integers a(1≤a≤2104),b(1≤b≤109),and their meanings are shown in the description.Contains most of the 12W test cases.
Output
For each set of input data,output a line of two integers,representing X, Y.If you cannot find such X and Y,output one line of "No Solution"(without quotation).
Sample Input
6 8
798 10780
Sample Output
No Solution
308 490
题目要求,对于给定的a和b,有x+y=a,lcm(x,y)=b;
(lcm为求最小公倍数)
对于数论这种玩意儿,其实我是懵逼的。老老实实看了下别人的题解,发现这其实是一个解一元二次方程的问题。
数字之间的关系如下:
a=x+y;
x
y=gcd(ab)b;
可以得到一个一元二次方程(推导关系在代码中)。
代码如下:

/*x+y=a;
xy=gcd(a,b)*b;
(z-x)(z-y)=z^2-(x+y)*z+xy;
Δt=√a*a-4*xy;
z1=((x+y)+Δt)/2;
z2=((x+y)-Δt)/2;
*/
#include<cmath>
#include<cstdio>
#include<cstring>
#include<iostream>
#define ll long long
using namespace std;
ll gcd(ll a,ll b)
{
    if(b==0)return a;
    return gcd(b,a%b);
}

int main()
{
    ll a,b;
    while(~scanf("%lld%lld",&a,&b))
    {
        ll xy=gcd(a,b)*b;
        if(a*a<4*xy)
        {
            printf("No Solution\n");
            continue;
        }
        double t=sqrt(a*a-4*xy);
        ll z1=((double)a+t)/2.0;
        ll z2=((double)a-t)/2.0;
        if((a-z1)*z1==xy)
        {
            printf("%lld %lld\n",a-z1,z1);
            continue;
        }
        if((a-z2)*z2==xy)
        {
            printf("%lld %lld\n",a-z2,z2);
            continue;
        }
        printf("No Solution\n");
    }
    return 0;
} 

相关文章

网友评论

      本文标题:A Simple Math Problem

      本文链接:https://www.haomeiwen.com/subject/ocjybttx.html