Problem Description

Given $L, R$, ask how many integers $x$ with $L \leq x \leq R$ satisfy that there exist integers $y, z$ such that $x = y^2 - z^2$.

Input Format

Input one line containing two integers $L, R$, separated by one space.

Output Format

Output one line containing one integer: the number of $x$ that satisfy the condition in the problem statement.

1 5

4

Hint

Sample Explanation

• $1 = 1^2 - 0^2$
• $3 = 2^2 - 1^2$
• $4 = 2^2 - 0^2$
• $5 = 3^2 - 2^2$

Constraints

For $40\%$ of the testdata, $L, R \leq 5000$.

For all testdata, $1 \leq L \leq R \leq 10^9$.

The 14th Lanqiao Cup Software Competition, Provincial Contest, C/C++ Undergraduate Group A, Problem C.

Translated by ChatGPT 5