一个不一样的证明

$$\sum_{i=1}^{x} \left\lfloor \dfrac{x}{i} \right\rfloor \bmod 2 = \left\lfloor \sqrt{x} \right\rfloor \bmod 2$$

的思路，不需要任何数论知识。

考虑反比例函数 $y=\dfrac{x}{i}$ 在第一象限内的图象：

注意到第一象限内 $y=\dfrac{x}{i}$ 下的整点集大小即为原式，且这个点集关于直线 $y=x$ 对称。

考虑将不在 $y=x$ 图象上的点两两对应，由于对 $2$ 取模，所以只考虑 $y=x$ 图象上点，数量是 $\sqrt{n}$ 个。

于是原结论成立，剩下的求 $\sum\limits_{i=1}^{n} \left( \left\lfloor \sqrt{x} \right\rfloor \bmod 2 \right)$ 是简单的，不再赘述。

另外这个题评 6 是不是太高了？

注意到内层等于 $1 \sim n$ 的因数个数和，而有且只有完全平方数有奇数个因数，因此原式等于：

$$\sum_{x=1}^{n} \left( \left\lfloor \sqrt x \right\rfloor \bmod 2 \right)$$

按 $\left\lfloor \sqrt{n} \right\rfloor$ 的奇偶性分类讨论推式子即可。

#include <bits/stdc++.h>
using namespace std;
int main()
{
	int T;
	scanf("%d", &T);
	while (T--)
	{
		long long n;
		scanf("%lld", &n);
		long long c = sqrtl(n + 0.5);
		if (c % 2 == 0) printf("%lld\n", c * (c + 1) / 2);
		if (c % 2 == 1) printf("%lld\n", c * (c - 1) / 2 + n - c * c + 1);
	}
	return 0;
}