[UVA][用線段樹建表] 10909 - Lucky Number
| 4th IIUC Inter-University Programming Contest, 2005 |
|
| E |
Lucky Number |
| Input: standard input |
|
| Problemsetter: Mohammed Shamsul Alam |
|
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 |
11 is not the sum of two luckies! |
題目很簡單，依序找到 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;
}