HDU 5974 A Simple Math Problem （数论+解方程组）

HDU 5974 A Simple Math Problem （数论+解方程组）

Problem Description

Given two positive integers a and b,find suitable X and Y to meet the conditions:X+Y=aLeast 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 8798 10780

Sample Output

No Solution308 490

题意

给出 X+Y=a 、 lcm(X,Y)=b ，其中 ​​a、b​​​ 是已知的，求 ​​X、Y​​ 。

思路

无意间自己想出的一个定理（虽然不知道数论里面有没有它）， gcd(a,b)=gcd(X,Y)

关于证明在比赛的时候还没有，只是感觉它是对的，可能是数学方面的感性吧~

证明过程：

首先有 gcd(a,b)=gcd(X+Y,lcm(X,Y))

我们令 k=gcd(X,Y) ，显然 k|X 、 k|Y ，于是有 X+Y=k×(Xk+Yk) ，并且 Xk、Yk

又因为 lcm(X,Y)=X×Yk ，它也就等价于 k×(Xk×Yk) ，因为互质的关系，显然， gcd(X+Y,lcm(X,Y))=k=gcd(X,Y)

于是这样便证明成功啦~ （只是还不知道它在什么情况下才会成立）

有了 gcd(X,Y) ，我们便可以知道 XY=lcm(X,Y)×gcd(X,Y)

然后因为 (X+Y)2−4XY=(X−Y)2 ，便可以计算出 X−Y

与 X+Y=a 联立方程组分别解出 ​​X、Y​​ 。

解不存在的情况： ​​X、Y​​​ 计算其最小公倍数如果不等于 ​​b​​ ，则解不存在。

AC 代码

#include#include#include#include#includeusing namespace std;#define MAXX 110000typedef __int64 LL;LL gcd(LL a,LL b){ if(b==0)return a; return gcd(b,a%b);}void solve(int a,int b){ LL gc=gcd(a,b); LL xy=b*gc; LL x_y=sqrt(a*a-4.0*xy); LL x=(a+x_y)/2; LL y=a-x; if(x/gcd(x,y)*y!=b) { printf("No Solution\n"); return; } if(x>y)swap(x,y); printf("%I64d %I64d\n",x,y);}int main(){ LL a,b; while(~scanf("%I64d%I64d",&a,&b)) solve(a,b); return 0;}

版权声明：本文内容由网络用户投稿，版权归原作者所有，本站不拥有其著作权，亦不承担相应法律责任。如果您发现本站中有涉嫌抄袭或描述失实的内容，请联系我们jiasou666@gmail.com 处理，核实后本网站将在24小时内删除侵权内容。