自动搬运

查看原文

来自洛谷，原作者为

	SUNCHAOYI 报名个人赛 https://www.luogu.com.cn/contest/44296

搬运于2025-08-24 22:19:08，当前版本为作者最后更新于2021-08-20 10:19:30，作者可能在搬运后再次修改，您可在原文处查看最新版

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

以下是正文

---

[SHOI2002]N的连续数拆分【数据加强版】

---

来一个和其它题解稍稍有些不一样的做法。

首先还是列出等式，设最小的正整数为 $l$，最大的正整数为 $r$，则由求和公式可列出式子：

$$\begin{cases} 0 < l \le r \le n\\ l,r \in \mathbb{N^*}\\ \dfrac{1}{2}(l + r) (r - l + 1) = n\\ \end{cases} $$

化简一下第二个式子便是 $(l + r) (r - l + 1) = 2n$，因此必须要有 $l + r \mid 2n$ 且 $r - l + 1 \mid 2n$。再设 $a = l + r,b = r - l + 1$，直接解得

$$\begin{cases} r = \dfrac{a + b - 1}{2}\\ l = a - r \end{cases} $$

显然当 $2 \mid a + b - 1$ 时才有正整数解。因此我们枚举 $2n$ 的因数，然后判断是否符合条件，然后累加答案。由于因数两两配对，所以时间复杂度为 $O(\sqrt{2n})$。核心代码如下：

int work (ll x)
{
	int cnt = 0;
	x <<= 1;
	for (ll i = 2;i * i <= x;++i)//记得为 long long
		if (x % i == 0)
			if ((i + x / i) & 1) ++cnt;
	return cnt;	
}

---

那么还有没有更优的解法呢？？

我们观察 $a,b$ 的奇偶性，因为 $2 \mid a + b - 1$ 才存在解，也就是 $a + b$ 一定为奇数。又因为只有在奇数与偶数相加时才得到奇数，所以 $a,b$ 必定为一奇一偶。所以可以将题目转化为求 $2n$ 的奇数因子，等同与求 $n$ 的奇数因子。

先将 $n$ 进行质因数分解 $n = \prod_{i = 1}^{k} p_i^{c_i}$，然后根据算数基本定理，除去唯一的偶质数 $2$ 后求奇数因数个数即可。因为质数中除了 $2$ 均为奇数，所以先预处理出 $\sqrt{n}$ 内的质数，然后再求因数时把所有 $2$ 除去即可。完整代码如下：

//这个方法在多组数据中会更优
#include <iostream>
#include <cstdio>
#include <cmath>
#define ll long long
using namespace std;
const int MAX = 3e7 + 5;
int cnt,p[MAX >> 1];//p 记录质数，显然 sqrt (n) 的一半足够了
ll n;
bool flag[MAX];
void pre (int x);
int main ()
{
	//先分解质因子，然后计算奇因子的个数
	
	scanf ("%lld",&n);
	pre ((int)sqrt (n));//枚举到 sqrt(n)
	int ans = 1;
	for (int j = 1;j <= cnt && (ll)p[j] * p[j] <= n;++j)//边界枚举
	{
		int k = 0;
		while (n % p[j] == 0)
		{
			if (j != 1) ++k;//第一个质数为 2
			n /= p[j];
		}
		ans *= (k + 1);//算数基本定理
	}
	if (n > 2) ans *= 2;//注意剩余的那个质数也需要是奇数才行
	printf ("%d\n",ans);
	return 0;
}
void pre (int x)//线性筛质数
{
	for (int i = 2;i <= x;++i)
	{
		if (!flag[i]) p[++cnt] = i;
		for (int j = 1;j <= cnt;++j)
		{
			if (i * p[j] > x) break;
			flag[i * p[j]] = 1;
			if (i % p[j] == 0) break;
		}
	}
}