Uốn vuông

View as PDF

Submit solution

All submissions

Best submissions

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~ là độ dài của sợi dây ngắn nhất để có thể bị uốn cong thành hình tam giác vuông có các cạnh là số nguyên.

Chúng ta có thể kể ra một số ví dụ khác như: ~24~: ~(6~, ~8~, ~10)~, ~30~: ~(5~, ~12~, ~13)~, ~36~: ~(9~, ~12~, ~15)~, ~40~: ~(8~, ~15~, ~17)~, ~48~: ~(12~, ~16~, ~20)~.

Sợi dây độ dài ~20~ không thể bị uốn thành một tam giác vuông có cạnh nguyên theo bất cứ cách nào.

Một số sợi dây với độ dài khác lại có thể uốn thành tam giác vuông có cạnh nguyên theo nhiều cách khác nhau, ví dụ ~120~: ~(30~, ~40~, ~50)~, ~(20~, ~48~, ~52)~, ~(24~, ~45~, ~51)~.

Gọi độ dài của dây là ~L~, hỏi có bao nhiêu giá trị ~L \leq N~ để có thể tạo ra duy nhất một tam giác vuông có cạnh nguyên?

Input

Gồm nhiều test, mỗi test nằm trên một dòng là số nguyên ~N \leq 20000000~.

Output

Ứng với mỗi test, in ra trên một dòng số lượng số ~L \leq N~ mà chỉ có thể tạo ra duy nhất ~1~ tam giác vuông.

Sample Input

12
30

Sample Output

1
3

Comments

Please read the guidelines before commenting.

There are no comments at the moment.