自动搬运

查看原文

来自洛谷，原作者为

	yaotianhao 我是菜逼 | B站关注wmrqwq喵

搬运于2025-08-24 21:15:40，当前版本为作者最后更新于2023-11-14 09:04:03，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

题意

求 $1$ 到 $n$ 中连续 $k$ 个数的和为完全平方数的个数。

分析

我们先按 $k$ 的奇偶性分讨一下：

如果 $k \bmod 2 = 1$，那么设中间的数为 $mid$，就可以算出这 $k$ 个数的和为 $k \times mid$，为了让这个和为完全平方数，所以 $mid$ 最小要为 $k$，之后就去枚举 $\times 1^2$、$\times 2^2$、$\times 3^2$，直到最后一个数超过 $n$。

如果 $k \bmod 2 = 0$，那么还是设中间的两个数为 $mid$ 和 $mid+1$，那这 $k$ 个数的和是 $\frac{(2 \times mid + 1)\times k}{2}$，然后把 $\frac{k}{2}$ 提取出来，因为它是个常数，不会变，然后就找与 $\frac{k}{2}$ 相乘为完全平方数的最小值，之后还是枚举 $\times 1^2$、$\times 2^2$、$\times 3^2$，再判一下是否有解。

代码

代码如下

#include <bits/stdc++.h>
#define int long long
using namespace std;
int n, k, sum, now = 1, ans;
signed main() {
	scanf("%lld%lld", &n, &k);
	if(k % 2 == 1) {
		for(int i = 1; ; i++) {
			if(k * i * i + k / 2 <= n) sum++;
			else break;
		}
		printf("%lld", sum);
	}
	else {
		int l = k / 2;
		for(int i = 2; i * i <= k; i++) while(l % (i * i) == 0) l /= i * i;
		if(l % 2 == 0) {
			printf("0");
			return 0;
		}
		for(int i = 1; ; i += 2) {
			ans = i * i * l;
			if(ans < k + 1) continue;
			if(ans / 2 + k / 2 <= n) sum++;
			else break;
		}
		printf("%lld", sum);
	}
}