题目描述

退役三年后，_rqy 成为了一名数学人。

有一天，求小真问了 _rqy 一个问题：是否存在一个三边长都为有理数的直角三角形，使得其面积恰好是 $1$?

_rqy 想了很久，发现肯定不存在。证明可以见本题目描述末尾。

作为一名数学人，_rqy 觉得自己应该具有推广问题的基本素养。所以她很好奇：对任意正整数 $n$，如何判断是否存在一个三边长都为有理数的直角三角形，使得其面积为 $n$？

例如对 $n=1$，答案是不存在。对 $n=6$，则存在：其是边长为 $3, 4, 5$ 的直角三角形的面积。

为了检验你是否也具有数学人的基本素养，_rqy 想让你求出 $L, \dots, R$ 中满足条件的数的个数。

输入格式

一行两个正整数 $L, R$。

输出格式

一行一个非负整数，表示答案。

1 6

2

1 100

50

1 100000

56490

数据范围与提示

对 30% 的数据，$1 \leqslant L \leqslant R \leqslant 10$。

对 50% 的数据，$1 \leqslant L \leqslant R \leqslant 100$。

另有 20% 的数据，$R - L \leqslant 3$。

对 100% 的数据，$1 \leqslant L \leqslant R \leqslant 5 \times 10^5$。

证明：1 不是有理边长的直角三角形的面积

显然这个问题等价于：是否存在一个三边长都是整数的直角三角形，其面积是完全平方数。

假如一个直角三角形三边长分别是 $a,b,c$ 而面积是 $d^2$，则 $a^2 + b^2 = c^2, ab = 2d^2$。我们知道勾股数一定长成 $a = 2mn, b = n^2 - m^2, c = n^2 + m^2$，其中 $m < n$ 并且他们互质且一奇一偶. 那么 $mn(n-m)(n+m) = d^2$. 由于 $n, m$ 互质，他们一定也和 $n-m,n+m$ 互质。所以 $n, m, n-m, n+m$ 都是完全平方数。

设 $n = p^2, m = q^2, n+m = r^2, n-m = s^2$. 由于 $n, m$ 一奇一偶，$n\pm m$都是奇数，所以 $r, s$ 都是奇数。记 $x = \frac{r + s}{2}, y = \frac{r-s}{2}$, 则 $x^2 + y^2 = \frac{r^2 + s^2}{2} = n = p^2$, 并且 $xy = \frac{r^2 - s^2}{4} = \frac{q^2}{2}$.

由于 $x, y$ 是整数，所以 $\frac{q^2}{2}$ 是整数，所以 $q$ 一定是偶数。因此以 $(x, y, p)$ 为三边长的直角三角形的面积是 $\frac{q^2}{4} = \bigl(\frac{q}{2}\bigr)^2$，也是完全平方数。

而 $\bigl(\frac{q}{2}\bigr)^2 = \frac{m}{4} < nm(n-m)(n+m) = d^2$, 所以我们得到了一个面积更小的满足条件的三角形。重复这个过程，那么面积会越来越小。但是面积总是整数，不能减到小于 $1$，所以矛盾。因此只可能根本不存在这样的三角形。