Problem Solving►UVa

UVa 10290 - {Sum+=i++} to Reach N

Contents

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

Problem

題目網址
中文網址

給你 N ，看 N 可以用幾組連續正整數的和表示。例如: 9 = 2 + 3 + 4 = 4 + 5 = 9 ， 輸出 3 組。

Solution

N 可以表示成連續的正整數，也就是 $N = A + (A + 1) + \cdots + (B - 1) + B$，可以寫成: ${(A+B)\times(A-B+1)}\over2$。

而 $A+B$ 和 $A-B+1$ 必定是一個奇數一個偶數，稍微假設一下 A 和 B 的奇偶狀況即可得知。而偶數的除以二，剩下的奇數就是 N 的因數，所以我們要求的就是 N 的奇因數個數。

作法: 先建出質數表，將數字先除以二直到不能除，剩下的去做質因數分解，再將各項的 次方+1 相乘起來，就是奇因數的個數了。因為質數除了 2 以外皆是奇數，奇數乘奇數仍然是奇數，也就是看有幾種組合了。

在建質數表時記得只需要建到 測資的開根號 ，除不完剩下的就是質數了，因為如果不是質數，他一定可以分解成其他質數(算術基本定理)，而這樣在前面就處理過了。(雖然實際上UVa的測資只需要建到 1e6 就可以了)

p.s. 0 要單獨出來處理

Code

UVa 10290UVa 10290 - {Sum+=i++} to Reach N
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57

#include<cstdio>
#include<cmath>
#define N 5000000
#define M 400000
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 j = i * i; j < N; j += i)
                sieve[j] = true;
    }

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

    LL n;
    while (scanf("%lld", &n) != EOF)
    {
        if (!n)
            puts("1");
        else
        {
            while (!(n % 2))
                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);
        }
    }

    return 0;
}