1487D.md (2016B)
1 Source: https://codeforces.com/problemset/problem/1487/D 2 3 D. Pythagorean Triples 4 5 time limit per test 6 7 2 seconds 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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)$. 22 23 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$. 24 25 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. 26 27 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 \le a \le b \le c \le n$ such that they are Pythagorean both according to his formula and the real definition? He asked you to count these triples. 28 29 Input 30 31 The first line contains one integer $t$ ($1 \le t \le 10^4$) — the number of test cases. 32 33 Each test case consists of one line containing one integer $n$ ($1 \le n \le 10^9$). 34 35 Output 36 37 For each test case, print one integer — the number of triples of integers $(a, b, c)$ with $1 \le a \le b \le c \le n$ such that they are Pythagorean according both to the real definition and to the formula Vasya came up with. 38 39 Example 40 41 Input 42 43 ``` 44 3 45 3 46 6 47 9 48 ``` 49 50 Output 51 52 ``` 53 0 54 1 55 1 56 ``` 57 58 Note 59 60 The only Pythagorean triple satisfying $c = a^2 - b$ with $1 \le a \le b \le c \le 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$.