B3879题解

yaotianhao · 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);
    }
}