HDU 5974"A Simple Math Problem"（GCD(a,b) = GCD(a+b,ab) = 1）

传送门

•题意

　　已知 $a,b$，求满足 $x+y=a\ ,\ LCM(x,y)=b$ 条件的 $x,y$；

　　其中，$a,b$ 为正整数，$x,y$ 为整数；

•题解

　　关键式子：设 $a,b$ 为正整数，如果有 $GCD(a,b)=1$，则有 $GCD(a+b,ab)=1$；

　　证明可以看这里【??】；

　　令 $p=\frac{x}{GCD(x,y)}\ ,\ q=\frac{y}{GCD(x,y)}$；

　　那么，将 $p,q$ 带入 $\begin{cases} x+y=a \\ LCM(x,y) &= \frac{xy}{GCD(x,y)} \\ &= b \end{cases}$ 得：$\begin{cases} (p+q)\cdot GCD(x,y) &= a \\ p\cdot q\cdot GCD(x,y) &=b \end{cases}$

　　即

　　　　　　$\begin{cases} (p+q)  &= \frac{a}{GCD(x,y)} \\ p\cdot q &=\frac{b}{GCD(x,y)} \end{cases}$

　　又因为 $GCD(p,q) = 1$，所以有 $GCD(p+q,pq)=GCD( \frac{a}{GCD(x,y)}\ ,\ \frac{b}{GCD(x,y)})=1$；

　　所以 $GCD(x,y)=GCD(a,b)$；

　　有了 $GCD(x,y)$ 的值，相当于已知 $a,b$，求满足 $x+y=a,xy=b\cdot GCD(x,y)$ 的整数解 $x,y$；

　　技巧，求解出 $x-y=\sqrt{(x+y)^2-4xy}$，判断 $x-y$ 是否为整数，如果不是，输出 "No Solution"；

•Code

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 #define ll long long
 4 #define GCD(a,b) __gcd(a,b)
 5 
 6 ll a,b;
 7 
 8 void Solve()
 9 {
10     b *= GCD(a,b);
11     ll tmp=a*a-4*b;
12     ll s=sqrt(tmp);
13     ///不用特判tmp < 0
14     ///如果 tmp < 0 , s=sqrt(tmp)=-INF
15     if(s*s != tmp || (a+s)%2 != 0)
16         return puts("No Solution"),void(0);
17 
18     ll x=(a+s)/2;
19     ll y=a-x;
20     printf("%lld %lld\n",min(x,y),max(x,y));
21 }
22 int main()
23 {
24     while(~scanf("%lld%lld",&a,&b))
25         Solve();
26 
27     return 0;
28 }

View Code

HDU 5974"A Simple Math Problem"（GCD(a,b) = GCD(a+b,ab) = 1）

原文：https://www.cnblogs.com/violet-acmer/p/11785370.html