HDU - 5974-A Simple Math Problem
题目大意:给你2个正整数a、b,要求你找出2个数x、y满足2个条件(1)x+y=a(2)x和y的最小公倍数是b,有则输出x、y,没有就输出“No Solution”
解题思路:首先按照正常的思路,分析题目,通过找b的因子来找到符合条件的x、y,b最大为10^9,也就是可以在sqrt(b)的时间复杂度内完成,但是题目是多组输出,也没有给你有多少组数据,所以按照这样思路的话大概率会TLE,头铁试了试,不出所料。这时我们就得想数学题常用的思路,当数据量过大时,一般可以从题目中找到公式,用线性的时间复杂度来完成。那么我们来看题目,假设x=qd,y=pd(p和q互质,gcd(x,y)=d);可得a=(p+q)d,b=pqdd;推出gcd(a,b)=d;根据x+y=a,xy/d=b;推出方程:xx-ax+bd=0;再根据求根公式X1=(-B+sqrt(BB-4AC))/(2A)、X2=(-B-sqrt(BB-4AC))/(2A)。注意求根公式的判别条件BB-4A*C>=0,另外这题要求X1和X2均为整数。
代码:
#include <bits/stdc++.h>
using namespace std;
int gcd(int a,int b)
{
return b?gcd(b,a%b):a;
}
int main()
{
int a,b;
while(~scanf("%d%d",&a,&b)){
int d=gcd(a,b);
int c=b*d;
int judge=a*a-4*c;
if(judge<0){
printf("No Solution\n");
}else{
double temp1=(a-sqrt(judge))/2;
int te1=(a-sqrt(judge))/2;
double temp2=(a+sqrt(judge))/2;
int te2=(a+sqrt(judge))/2;
if(temp1!=te1||temp2!=te2)printf("No Solution\n");
else{
printf("%d %d\n",te1,te2);
}
}
}
return 0;
}