题目来源

一、题目

A Pythagorean triple is a triple of integer numbers (a,b,c) such that it is possible to form a right triangle with the lengths of the first cathetus, the second cathetus and the hypotenuse equal to a, b and c, respectively. An example of the Pythagorean triple is (3,4,5).
Vasya studies the properties of right triangles, and he uses a formula that determines if some triple of integers is Pythagorean. Unfortunately, he has forgotten the exact formula; he remembers only that the formula was some equation with squares. So, he came up with the following formula: c=a^2−b.
Obviously, this is not the right formula to check if a triple of numbers is Pythagorean. But, to Vasya’s surprise, it actually worked on the triple (3,4,5): 5=3^2−4, so, according to Vasya’s formula, it is a Pythagorean triple.
When Vasya found the right formula (and understood that his formula is wrong), he wondered: how many are there triples of integers (a,b,c) with 1≤a≤b≤c≤n such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples.

给定n，问多少1≤a≤b≤c≤n，使直角三角形 (a,b,c) 满足c=a^2−b

二、输入

The first line contains one integer t (1≤t≤104) — the number of test cases.
Each test case consists of one line containing one integer n (1≤n≤109).

第一行测试样例数t
第二行整数n

三、输出

For each test case, print one integer — the number of triples of integers (a,b,c) with 1≤a≤b≤c≤n such that they are Pythagorean according both to the real definition and to the formula Vasya came up with.

满足条件的三角形数量

四、样例

input:

3
3
6
9

output:

0
1
1

Note
The only Pythagorean triple satisfying c=a2−b with 1≤a≤b≤c≤9 is (3,4,5); that’s why the answer for n=3 is 0, and the answer for n=6 (and for n=9) is 1.

五、思路 + 代码

1. 联立 c 2 = a 2 + b 2 c^2=a^2+b^2 c2=a2+b2 与 c = a 2 − b c=a^2-b c=a2−b 得 c 2 = b + c + b 2 c^2=b+c+b^2 c2=b+c+b2
2. 整理得 ( c + b ) ( c − b ) = b + c (c+b)(c-b)=b+c (c+b)(c−b)=b+c 即 c = b + 1 c=b+1 c=b+1
3. 将 c = b + 1 c=b+1 c=b+1代入 c = a 2 − b c=a^2-b c=a2−b 得 b = a 2 − 1 2 b=\frac{a^2-1}{2} b=2a2−1​

整理得:

1. a = a a=a a=a
2. b = a 2 − 1 2 b=\frac{a^2-1}{2} b=2a2−1​
3. c = a 2 + 1 2 c=\frac{a^2+1}{2} c=2a2+1​

对于a,b,c须满足:

1. a , b , c a,b,c a,b,c皆为正整数,所以 a 2 − 1 2 \frac{a^2-1}{2} 2a2−1​与 a 2 + 1 2 \frac{a^2+1}{2} 2a2+1​要为正整数，所以a要为奇数
2. a > 0 a>0 a>0
3. b > = a b>=a b>=a即 b = a 2 − 1 2 > = a b=\frac{a^2-1}{2}>=a b=2a2−1​>=a得 a > = 2 a>=2 a>=2
4. c > b c>b c>b即 a 2 + 1 2 > a 2 − 1 2 \frac{a^2+1}{2}>\frac{a^2-1}{2} 2a2+1​>2a2−1​显然成立

综上，满足 a 2 + 1 2 < = n \frac{a^2+1}{2}<=n 2a2+1​<=n的所有奇数 a ( a > = 3 ) a(a>=3) a(a>=3)的个数即为所求。

代码如下：

#include<iostream>
using namespace std;
typedef long long ll;
ll n;
int main() {
	int t;
	cin >> t;
	while (t--) {
		ll cnt = 0;
		cin >> n;
		for (ll a = 3; (a * a + 1) / 2 <= n; a += 2) {
			cnt++;
		}
		cout << cnt << endl;
	}
	return 0;
}