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
即
因为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;
}