洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解
洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解
题目链接:B3879 [信息与未来 2015] 连续数的和(加强版)
本题弱化版:B3878 [信息与未来 2015] 连续数的和
题目描述:
给出两个整数 \(n\) 和 \(k\),求出 \(1\sim n\) 中连续 \(k\) 个数的和为完全平方数的个数。
输入格式:
一行两个整数 \(n,k\)。
输出格式:
一行一个整数,即 \(1\sim n\) 中连续 \(k\) 个数的和为平方数的个数。
数据范围:
\(2\le n\le 10^{10},1\le k\le n\)。
有史以来调了最久的简单题,代码水平简直是惨不忍睹。
根据等差数列求和公式,区间 \([x, x + k - 1]\,(x \in \mathbb{Z}_+)\) 的正整数之和为 \[ \begin{aligned} S &= kx + \frac{k(k-1)}{2} \\[8pt] &= k\left(\frac{k - 1}{2} + x\right) \end{aligned} \] 记 \(k=ab^2\) ,其中 \(b\) 为满足条件的最大正整数。\(k\) 是已知的,因此 \(a,b\) 是固定的。
当 \(k\) 为奇数时,若 \(x\) 合法则一定有 \[ \exists\, c \in \mathbb{Z}_+ \quad\mathbf{s.t.}\quad \left(\frac{k - 1}{2} + x\right) = ac^2 \] 考虑枚举所有可能的 \(c\) ,则 \[ x = ac^2 - \frac{k - 1}{2} \] 然后检查 \(x\) 是否合法即可。
当 \(k\) 为偶数时,不妨重新记 \(k=2ab^2\) ,其中 \(b\) 为满足条件的最大正整数,则 \[ \begin{aligned} S &= k\left(\frac{k - 1}{2} + x\right) \\[8pt]&= 2ab^2\left(ab^2 + x - \frac{1}{2}\right) \\[8pt] &= ab^2(2ab^2 + 2x - 1) \\[8pt] &= ab^2(k + 2x - 1) \end{aligned} \] 接下来和之前是同理的(注意这里的 \(a\) 和之前的定义不同) \[ \exists\, c \in \mathbb{Z}_+ \quad\mathbf{s.t.}\quad (k + 2x - 1) = ac^2 \] 依旧考虑枚举所有可能的 \(c\) ,则 \[ x = \frac{(ac^2 + 1 - k)}{2} \] 然后检查 \(x\) 是否合法即可。
时间复杂度 \(O\left(\sqrt{k}\right)\)
代码:
#include <bits/stdc++.h>
using namespace std;
#define int long long
#define INF 0x3f3f3f3f3f3f3f3f
template<typename T> void up(T &x, T y) { x < y ? x = y : 0; }
template<typename T> void down(T &x, T y) { x > y ? x = y : 0; }
#define rep(i, a, b) for(int i = (a), i##END = (b); i <= i##END; i++)
#define Rep(i, a, b) for(int i = (a), i##END = (b); i >= i##END; i--)
#define N ((int)())
int n, k, ans;
signed main()
{
ios::sync_with_stdio(0);
cin.tie(0); cout.tie(0);
// freopen("check.in","r",stdin);
// freopen("check.out","w",stdout);
cin >> n >> k;
if(k & 1)
{
int a = k, b = 1;
rep(i, 2, (int)sqrt(k) + 5) if(a % (i * i) == 0) { a /= i * i, b *= i; }
for(int c = 1; ; c++)
{
static int x; x = a * c * c - (k - 1) / 2;
if(x + k - 1 > n) break;
if(x >= 1) ++ans;
}
}else
{
int a = k / 2, b = 1;
rep(i, 2, (int)sqrt(k) + 5) if(a % (i * i) == 0) { a /= i * i, b *= i; }
for(int c = 1; ; c++)
{
static int x; x = (a * c * c + 1 - k);
if(x / 2 + k - 1 > n) break;
if(((x & 1) == 0) && x / 2 >= 1) ++ans;
}
}
cout << ans << '\n';
return 0;
}
写到这才发现代码里根本不需要计算变量 \(b\) 。

![洛谷B3883 [信息与未来 2015] 求回文数(加强版) & B3882 题解](/qwq/img/p216.webp)
![洛谷B3879 [信息与未来 2015] 连续数的和(加强版) & B3878 题解](/qwq/img/p233.webp)

