HDU 5974 A Simple Math Problem

A Simple Math Problem

Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 8456 Accepted Submission(s): 2677

Problem Description


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≤2*10^4),b(1≤b≤10^9),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满足 x+y=a&&LCM(x,y)=b,如果有请输出x和y，否则就输出 No Solution

解题思路：已知：x+y=a,LCM(x,y)=b

　　　　　　　　y=a-x;

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

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

　　　　　　　　如果把gcd(x,y)当成已知的话，就是求x的一元二次方程

　　　　　　　　我们分析可知gcd(x,y)==gcd(a,b)

　　　　　　　　设y=k*x

　　　　　　　　∵gcd(x+y,x)==gcd((k+1)x,x)因为他们有相同的因子

　　　　　　　　b=x*y/gcd(x,y)=k*x,a=(k+1)x,所以gcd(x,y)==gcd(a,b)

　　　　　　　　(有点语无伦次，这个好象是同余定理来着，读者请自己脑海中想象一下）

　　　　　　　　然后可得：x=(n+sqrt(n*n-4*__gcd(n,m)*m))/2.0

　　　　　　　如果x是整数说明存在x和y否则不存在

　　　　　　　　可以得到如下代码：

#include<bits/stdc++.h>
using namespace std;
int main()
{
    long long n,m,a2;
    while(~scanf("%lld%lld",&n,&m))
    {
        double a1=(n+sqrt(n*n-4*__gcd(n,m)*m))/2.0;
        a2=a1;
        if(a1==a2)
        printf("%lld %lld
",n-a2,a2);
        else
        puts("No Solution");
    }
    return 0;
}

AC：