这是个数论题,题目给出两个正整数a,b;
让我们寻找两个正整数X,Y,其满足X+Y=a,LCM(X,Y)=b;
这个题可以用解方程做;
因为XY=LCM(X,Y)GCD(X,Y);LCM(X,Y)=b;GCD(X,Y)=GCD(a,b);
所以XY=bGCD(a,b);
(z-x)(z-y)=zz-(x+y)z+xy;
△t△t=(x+y)^2-4xy;
z1=((x+y)+△t)/2 , z2=((x+y)-△t)/2 ;
显然当△t<0方程无解,△t不是整数时,x,y也不是整数,所以这;两种时输出no solution;
其他情况直接输出z1,z2;
还有因为 integers a(1≤a≤2*104),b(1≤b≤109),所以变量 a,b,x,y,t 要用long long声明;
#include<stdio.h>
#include<math.h>
int gcd(int a,int b)
{
return b==0? a:gcd(b,a%b);
}
int main()
{
long long a,b,x,y,t;
while(~scanf("%lld%lld",&a,&b))
{
b=gcd(a,b)*b;
if(a*a-4*b<0)
{
printf("No Solution\n");
}
else
{
t=sqrt(a*a-4*b);
x=(a+t)/2;
y=x-t;
if(t*t==a*a-4*b)
{
printf("%lld %lld\n",y,x);
continue;
}
else
{
printf("No Solution\n");
}
}
}
}
网友评论