ZeroJudge d756 - 10290 - {Sum+=i++} to Reach N

Contents

1. 1. Problem
2. 2. Solution
3. 3. Code

Problem

題目網址

給你 N ，看 N 可以用幾組連續 非負整數 的和表示。例如: 6 = 0 + 1 + 2 + 3 = 1 + 2 + 3 = 6 ， 輸出 3 組。

Solution

跟 UVa 10290 差不多，只是測資比較嚴，然後需要處理 0 開始加的問題。

透過上一題可以知道連續非負整數也可以表示成以下，而從 0 開始加的話:

$$\begin{aligned} &B = 0 \\\\ &\frac {(A+B) \times (A-B+1)}{2} = \frac {A \times (A+1)}{2} \end{aligned}$$

利用此方式，將 $N$ 乘 $2$ 後，判斷是否存在 $A$ 使的 $A\times(A+1)=N\times2$ 。可以利用將 $N\times2$ 開根號後來試。

bool haveZero = false;
LL Sqrt = (LL)sqrt(n << 1);
if (Sqrt*(Sqrt + 1) == n << 1)
    haveZero = true;

速度方面，因為測資較大，可能會超時，在建質數表時稍微改進了一下寫法。而在做因數分解時，本來是 n >= prime[idx] 時就繼續做，但可以改成 n >= prime[idx] * prime[idx] 會快不少(感謝Morris提醒)，因為接下來如果 n 不是質數，則可以寫成 2 個質數相乘的話，n 一定大於等於 目前質數*目前質數 ，不然就是 n 為質數了。

Code

ZJ d756ZJ d756

#include<cstdio>
#include<cmath>
#define N 30000001
#define M 2000000
typedef long long LL;

bool sieve[N] = { true, true };
LL prime[M];
int main()
{
    int  count = 0, i, s = sqrt(N);
    //get prime
    for (i = 2; i < s; i++)
    {
        if (!sieve[i])
        {
            for (int k = (N - 1) / i; k >= i; k--)
                if (!sieve[k])
                    sieve[k*i] = true;
        }
    }

    for (i = 2; i < N; i++)
        if (!sieve[i])
            prime[count++] = i;

    //input
    LL n;
    while (scanf("%lld", &n) != EOF)
    {
        if (!n)
            puts("1");
        else
        {
            //判斷是否可從 0 開始加
            bool haveZero = false;
            LL Sqrt = (LL)sqrt(n << 1);
            if (Sqrt*(Sqrt + 1) == n << 1)
                haveZero = true;

            while (!(n & 1))
                n >>= 1;
            
            //因數分解
            int sum = 1, idx = 1;//從 3 開始
            while (n != 1 && n >= prime[idx] * prime[idx] && idx < count)
            {
                int temp = 1;
                while (!(n%prime[idx]))
                {
                    temp++;
                    n /= prime[idx];
                }
                sum *= temp;
                idx++;
            }
            
            //如果還有剩下沒除完的數，就是質數
            if (n != 1)
                sum <<= 1;

            printf("%d\n", sum + (haveZero ? 1 : 0));
        }
    }

    return 0;
}