Uốn vuông

View as PDF

Submit solution

Points: 1.10 (partial)
Time limit: 3.0s
Memory limit: 512M
Input: stdin
Output: stdout

Problem source:
HSPC 2014
Problem types
Allowed languages
C, C++, Go, Java, Kotlin, Pascal, PyPy, Python, Rust, Scratch

~12~ là độ dài của sợi dây ngắn nhất để có thể bị uốn cong thành hình tam giác vuông có các cạnh là số nguyên.

Chúng ta có thể kể ra một số ví dụ khác như: ~24~: ~(6~, ~8~, ~10)~, ~30~: ~(5~, ~12~, ~13)~, ~36~: ~(9~, ~12~, ~15)~, ~40~: ~(8~, ~15~, ~17)~, ~48~: ~(12~, ~16~, ~20)~.

Sợi dây độ dài ~20~ không thể bị uốn thành một tam giác vuông có cạnh nguyên theo bất cứ cách nào.

Một số sợi dây với độ dài khác lại có thể uốn thành tam giác vuông có cạnh nguyên theo nhiều cách khác nhau, ví dụ ~120~: ~(30~, ~40~, ~50)~, ~(20~, ~48~, ~52)~, ~(24~, ~45~, ~51)~.

Gọi độ dài của dây là ~L~, hỏi có bao nhiêu giá trị ~L \leq N~ để có thể tạo ra duy nhất một tam giác vuông có cạnh nguyên?

Input

Gồm nhiều test, mỗi test nằm trên một dòng là số nguyên ~N \leq 20000000~.

Output

Ứng với mỗi test, in ra trên một dòng số lượng số ~L \leq N~ mà chỉ có thể tạo ra duy nhất ~1~ tam giác vuông.

Sample Input

12
30

Sample Output

1
3

Comments

Please read the guidelines before commenting.


There are no comments at the moment.