[UVA][用線段樹建表] 10909 - Lucky Number＠Morris' Blog

2013-05-08 07:32:48| 人氣1,269| 回應0 | 上一篇 | 下一篇

[UVA][用線段樹建表] 10909 - Lucky Number

推薦 0 收藏 0 轉貼0 訂閱站台

4^th IIUC Inter-University Programming Contest, 2005
E	Lucky Number
	Input: standard input Output: standard output
	Problemsetter: Mohammed Shamsul Alam Special Thanks: Tanveer Hasan Saaem

Lucky numbers are defined by a variation of the well-known sieve of Eratosthenes. Beginning with the natural numbers strike out all even ones, leaving the odd numbers 1, 3, 5, 7, 9, 11, 13, ... The second number is 3, next strike out every third number, leaving 1, 3, 7, 9, 13, ... The third number is 7, next strike out every seventh number and continue this process infinite number of times. The numbers surviving are called lucky numbers. The first few lucky numbers are:

1, 3, 7, 9, 13, 15, 21, 25, 31, 33, … …

In this problem your task is to test whether a number can be written as the sum of two lucky numbers.

Input

The input file contains at most 100000 lines of input. Each line contains a single integer n (0 < n ≤ 2000000). Input is terminated by end of file.

Output

For each line of input produce one line of output. This line should be of one of the following types depending on whether n is expressible as the sum of two lucky numbers.

n is not the sum of two luckies!
n is the sum of L1 and L2.

For the second case, always make sure that (L2-L1) is nonnegative and minimized.

Sample Input	Output for Sample Input
11 12	11 is not the sum of two luckies! 12 is the sum of 3 and 9.

題目很簡單，依序找到 lucky number, 並且把位置是 lucky number 的倍數給刪除。

但是這個操作可能會很慢，因此使用線段樹，也就是靜態樹去完成。
讓刪除位置第 k 個的數字可以達到 O(logn)

詳細可以參考 zkw 式線段樹，又或者直接看代碼。

#include <stdio.h>
#include <algorithm>
using namespace std;
int st[(1<<22)+1];
int lucky[262144] = {1, 3};
int main() {
    int M;
    int n = 2000000;
    int i, j, k;
    for(M = 1; M < n+2; M <<= 1);
    for(i = 2*M-1; i > 0; i--) {
        if(i >= M)
            st[i] = (i-M)&1; // odd;
        else
            st[i] = st[i<<1] + st[i<<1|1];
    }
    int idx = 3;
    int pos, m, s;
    for(i = 1; idx <= 2000000; i++) {
        lucky[i] = idx;
        pos = 0;
        int cnt = 0;
        while(true) {
            pos += lucky[i], m = pos-cnt;
            //printf("m = %d\n", m);
            for(s = 1; s < M;) {
                if(st[s<<1] < m)
                    m -= st[s<<1], s = s<<1|1;
                else
                    s = s<<1;
            }
            if(s-M > 2000000)
                break;
            //printf("kill %d %d %d\n", pos, s-M, m);
            //getchar();
            cnt++;
            while(s)    st[s]--, s >>= 1;
        }
        idx++;
        while(st[idx+M] == 0)
            idx++;
    }
    m = i;
    while(scanf("%d", &n) == 1) {
        if(n&1) {
            printf("%d is not the sum of two luckies!\n", n);
            continue;
        }
        int pos = lower_bound(lucky, lucky+m, n/2)-lucky;
        for(i = pos; i >= 0; i--) {
            if(st[n-lucky[i]+M] && lucky[i] <= n-lucky[i]) {
                printf("%d is the sum of %d and %d.\n", n, lucky[i], n-lucky[i]);
                break;
            }
        }
        if(i < 0) {
            printf("%d is not the sum of two luckies!\n", n);
            continue;
        }
    }
    return 0;
}

我要檢舉

#10909#Lucky Number#建表

台長： Morris

您可能對以下文章有興趣

[UVA][黑白棋] 220 - Othello

[UVA] 377 - Cowculations

[UVA][高斯、逆元] 684 - Integral Determinant

[UVA][模擬] 654 - Ratio

人氣(1,269) | 回應(0)| 推薦 (0)| 收藏 (0)| 轉寄
全站分類: 不分類 | 個人分類: UVA |
此分類下一篇:[UVA][最鄰近點對] 11378 - Bey Battle
此分類上一篇:[UVA][dijkstra] 11367 - Full Tank?

回應(0)