题解：P6267 [SHOI2002]N的连续数拆分

[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;
        }
    }
}