题解 【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;
        }
    }
}