Codeforces 938C(数学)

Codeforces 938C
题意:求$n^2-(\frac nm)^2=x​$的一组解$n,m​$

易得$n^2-(\frac nm)^2=x \Longleftrightarrow (n-\frac nm)(n + \frac nm)=x$
设$a=n-\frac nm, b =n + \frac nm$
则$ab=x, n = \frac{a+b}2, m = \frac n{b-n}$
只要枚举$a:1 \rightarrow \sqrt{x}$,算出$b$(此处必须$ab=x$, 即整除),就能算出$n,m$的值(此处不一定要整除),然后利用$n^2-(\frac nm)^2=x$检验$n,m$即可

Codeforces Submission

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
#include<cstdio>
#include<algorithm>
#include<cstring>
#include<vector>
#include<queue>
#include<cmath>
using namespace std;
#define ms(i, j) memset(i, j, sizeof i)
#define ll long long
ll x;
void clean() {
}
int solve() {
scanf("%I64d", &x);
clean();
if (x == 0) return printf("1 1\n"), 0;
for (ll a = 1; a <= sqrt(x); a++) {
ll b = x / a;
if (x % a != 0) continue;
if ((a + b) % 2 != 0) continue;
ll n = (a + b) / 2;
if (b - n == 0) continue;
ll m = n / (b - n);
if (n * n - (n / m) * (n / m) == x) {
return printf("%I64d %I64d\n", n, m), 0;
}
}
return printf("-1\n"), 0;
}
int main() {
int T; scanf("%d", &T);
while (T--) solve();
return 0;
}
------ 本文结束 ------