一个简单的数学问题

发布日期: 2018-12-10

文章字数: 489

阅读时长: 3 分

阅读次数:

A Simple Math Problem
Time Limit: 2000/1000 MS (Java/Others) Memory Limit: 65536/65536 K (Java/Others)
Total Submission(s): 729 Accepted Submission(s): 177

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来满足条件   (1)X + Y =a  
                                           (2)（X，Y)的最小公倍数= b

即

x+y=a

xy/gcd(x,y)=b

令gcd(x,y)=tem

x=ic,y=jc

ic+jc=a

cij=b

tem(i+j)=a

temij=b

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

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

//思路：解一个二元一次方程求出方程根
//令A=a/tem;
//令B=b/tem;
//A=a/tem;
//B=b/tem;
//k1+k2=A;
//k1k2=B;
//k1(A-k1)=B;
// k1^2-Ak1+B=0;
// A^A-4B>0

#include<stdio.h>
#include<string.h>
#include<math.h>
#define M 100003
int gcd(int a,int b){if(b==0) return a;else return gcd(b,a%b);}
int main(){
    long int a,b,x,y,x2,y2,tem,k1,k2,A,B,q;
    while(scanf("%ld%ld",&a,&b)!=EOF){
             tem=gcd(a,b);
             A=a/tem;
             B=b/tem;
            q=A*A-4*B;
             if(q<0) printf("No Solution\n");
             else
             { long int  t1=sqrt(q);
                if(t1*t1!=q)printf("No Solution\n");
                else{
                       x=(A-t1)*tem;
                       y=(A+t1)*tem;
                       printf("%ld %ld\n",x/2,y/2);
                }

         <span class="token punctuation">}</span>
     <span class="token punctuation">}</span>
<span class="token keyword">return</span> <span class="token number">0</span><span class="token punctuation">;</span>
}