显然 $N \times 1$ 的长方形必须平行于坐标轴摆放，否则连不出长度为 $1$ 的边。

考虑将 $\sqrt{N}$ 提出一部分得到 $P\sqrt{Q}$，此时长度为 $\sqrt{Q}$ 的边必须存在于长方形内，这要求存在非负整数 $X$ 使得 $Q = X^2 + 1$（特别地，$X = 0$ 时 $Q = 1$，此时 $\sqrt{N}$ 是整数。

此时画出赵爽弦图，沿三角形的斜边取最小的格点直角三角形（然后可以两两配对形成 $Q \times 1$ 的长方形），剩下的全部切成 $1 \times 1$ 的小正方形，我们便完成了构造。

综上，「七巧板数」就是能表示为 $P^2 (X^2 + 1)$ 的正整数，其中 $P$ 为正整数，$X$ 为非负整数。

注意到 $X \le \sqrt{n}$，而单个 $X$ 下的「七巧板数」大约只有 $\dfrac{\sqrt{n}}{X}$ 个，因此给定范围内的「七巧板数」大约只有 $\dfrac{1}{2} \sqrt{n} \ln n$ 个，可以直接枚举后做前缀和回答询问。

最终的时间复杂度为 $O(\sqrt{n} \log^2 n + q \log n)$，空间复杂度为 $O(\sqrt{n} \log n)$。

#include <bits/stdc++.h>
using namespace std;
long long a[2000012];
long long sum[2000012];
long long get(long long x, int s)
{
	int l = 0, r = s;
	while (l < r)
	{
		int mid = (l + r + 1) >> 1;
		if (a[mid] <= x) l = mid;
		if (a[mid] > x) r = mid - 1;
	}
	return sum[l];
}
int main()
{
	ios::sync_with_stdio(0);
	long long n, q, s = 0;
	cin >> n >> q;
	for (long long i = 0; i * i + 1 <= n; i++)
		for (long long j = 1; (i * i + 1) * (j * j) <= n; j++)
		{
			s++;
			a[s] = (i * i + 1) * (j * j);
		}
	sort(a + 1, a + s + 1);
	s = unique(a + 1, a + s + 1) - a - 1;
	for (int i = 1; i <= s; i++)
		sum[i] = sum[i - 1] + a[i];
	while (q--)
	{
		long long l, r;
		cin >> l >> r;
		cout << get(r, s) - get(l - 1, s) << '\n';
	}
	return 0;
}