【二分】Pythagorean Triples—CF1487D

Pythagorean Triples—CF1487D

思路

联立 $a^2=b+c^2$、$a^2+b^2=c^2$ 得：
$a^2=2\ast c-1$、$b=c-1$。

对于一个固定的 $a$，$b$、$c$ 的值都是固定的，只要满足 $a\le b$ 和 $c\le n$ 即可。

使用二分可以求出对应的 $c$ 的值满足条件的 $a$ 的取值范围，另外要排除 $a=1,2$ 这两个值，因为这时候 $a>b$。

$Code$

#include 
#define int long long
#define sz(a) ((int)a.size())
#define all(a) a.begin(), a.end()
using namespace std;
using PII = pair<int, int>;
using i128 = __int128;
const int N = 2e5 + 10;

int n;

// c的值是否符合条件（先不考虑奇数这个条件）
int judge(int a) {
	if ((a * a + 1) / 2 <= n
		&& a <=(a * a + 1) / 2 - 1) {
		return 1;
	}
	return 0;
}

void solve() {
	cin >> n;
	cout << "       ";
	
	if (n <= 2) {
		cout << 0 << "\n";
		return;
	}
	
	// 二分求a的最大值（先不考虑得到的c是否是整数）
	int l = 3, r = n;
	while (l < r) {
		int mid = (l + r + 1) / 2;
		if (judge(mid)) {
			l = mid;
		} else {
			r = mid - 1;
		}
	}
	if (l % 2 == 0) {
		l --;
	}
	
	// 现在满足条件的a的取值范围是[3, l]中的所有奇数
	if (judge(l)) {
		cout << l / 2 << "\n";
	} else {
		cout << "0\n";
	}
}

signed main() {
	ios::sync_with_stdio(0), cin.tie(0), cout.tie(0);
	int T = 1;
	cin >> T; cin.get();
	while (T --) solve();
	return 0;
}
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
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58