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

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

                                            令gcd(x,y)=tem

                                                   x=i*c,y=j*c

                                                  i*c+j*c=a

                                                 c*i*j=b

                                                  tem*(i+j)=a

                                                   tem*i*j=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;
            //k1*k2=B;
            //k1(A-k1)=B;
            // k1^2-Ak1+B=0;
            // A^A-4*B>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);
		 	   }
		 		
		 	}
		 }
	return 0;
}