题目大意
给定p,q求解满足p/q=a/b+b/a的a,b。如果无解输出
0 0
求根公式做法
令x = a / b
原式转换为求该式的整数解
x
2
−
p
q
x
+
1
=
0
x^2-\frac{p}{q}x+1=0
x
2
−
q
p
x
+
1
=
0
x
=
p
q
+
p
2
q
2
−
4
2
x = \frac{\frac{p}{q}+\sqrt{\frac{p^2}{q^2}-4}}{2}
x
=
2
q
p
+
q
2
p
2
−
4
x
=
p
+
p
2
−
4
q
2
2
q
=
a
b
x=\frac{p+\sqrt{p^2-4q^2}}{2q}=\frac{a}{b}
x
=
2
q
p
+
p
2
−
4
q
2
=
b
a
只需判断
p
2
−
4
q
2
\sqrt{p^2-4q^2}
p
2
−
4
q
2
是否为整数即可确定a b是否为0
#include <iostream>
#include <cmath>
using namespace std;
using ll = long long;
int main()
{
int T;
cin >> T;
while (T--)
{
ll p, q;
cin >> p >> q;
ll d = p * p - 4 * q * q;
ll t = 0;
if (d >= 0) t = sqrt(d);
if (t * t != d) cout << 0 << ' ' << 0 << endl;
else cout << p + t << ' ' << 2 * q << endl;
}
return 0;
}
数论做法
p
q
=
a
2
+
b
2
a
b
\frac{p}{q}=\frac{a^2+b^2}{ab}
q
p
=
a
b
a
2
+
b
2
不妨假设
gcd(p,q)=1
（如果不满足则约分后满足）。
gcd(a^2+b^2, ab)=1
q=ab
若
p/q<2
则无解
枚举a，通过q求出b，然后判断a，b是否满足p
#include <iostream>
using namespace std;
using ll = long long;
int gcd(int a, int b)
{
if (b == 0) return a;
return gcd(b, a % b);
}
void solve()
{
int p, q;
cin >> p >> q;
int g = gcd(p, q);
p /= g;
q /= g;
if (p < 2 * q)
{
cout << 0 << ' ' << 0 << endl;
return;
}
for (int i = 1; i * i <= q; i++)
{
if (q % i) continue;
int j = q / i;
if (1ll * i * i + 1ll * j * j == p)
{
cout << i << ' ' << j << endl;
return;
}
}
cout << 0 << ' ' << 0 << endl;
return;
}
int main()
{
int T;
cin >> T;
while (T--)
{
solve();
}
return 0;
}