注意到七巧板数必然为 $(i^2+1) \times j^2( i \in \mathbb N^*,j \in \mathbb N)$。

由于 $n \le 10^{10}$，且七巧板数的分布很稀疏，直接枚举所有满足 $(i^2+1) \times j^2 \le n$ 的 $(i,j)$，询问用二分 + 前缀和即可。

时间复杂度为 $O(\sqrt{n} \log^2 n + q \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;
}