HDU 5974 A Simple Math Problem （gcd)

A Simple Math Problem

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

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

Source

2016ACM/ICPC亚洲区大连站-重现赛（感谢大连海事大学）

Recommend

wange2014

题意为找出满足x+y=a且x,y的最小公倍数等于b的 x y

分析：该题的数据范围很大，测试组数很多，需要算法有较小的复杂度或者预处理

最小公倍数与gcd是紧密相连的，从题目中可以发现 gcd(a,b)=gcd(x,y);

那么另令k=gcd(a,b) b=(x*y)/k b/k=(x/k)*(y/k)

a1=a/k,b1=b/k; x=l*k,y=(a1-l)*k;

然后通过二分找到对应的l值即可

代码如下：

#include <cstdio>
#include <iostream>
#include <cstring>
#include <algorithm>
using namespace std;
int main()
{
    int a,b,k,a1,b1,l,r,mid;
    while(scanf("%d%d",&a,&b)!=EOF)
    {
        k=__gcd(a,b);
        a1=a/k;b1=b/k;
        l=0;
        r=a1/2+1;
        while(l+1<r)
        {
         mid=(l+r)>>1;
         if(mid*(a1-mid)<=b1)
            l=mid;
         else
            r=mid;
        }
        if(l*(a1-l)!=b1)puts("No Solution");
        else printf("%d %d
",l*k,(a1-l)*k);
    }
    return 0;
}