解題區/解題區 - UVa

UVa 12039 - Goldbach's Cardinality

contents

  1. 1. Problem
  2. 2. Sample Input
  3. 3. Sample Output
  4. 4. Solution

Problem

求任兩個相異質數總和介於 [L, R] 之間的個數。

Sample Input

1
2
3
10 20
30 40
0 0

Sample Output

1
2
9
16

Solution

一開始使用 O(n log n) 的二分解法，但是遲遲沒有通過，最後改用 O(n) 的方式遞減 index。

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
#include <stdio.h>
#include <algorithm>
using namespace std;
#define maxL (10000000>>5)+1
#define GET(x) (mark[x>>5]>>(x&31)&1)
#define SET(x) (mark[x>>5] |= 1<<(x&31))
int mark[maxL];
int P[1048576], Pt = 0;
void sieve() {
    register int i, j, k;
    SET(1);
    int n = 10000000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(k = n/i, j = i*k; k >= i; k--, j -= i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
long long g(int n) {
    long long ret = 0;
    int pos = (int)(upper_bound(P+1, P+Pt, n) - (P+1));
    for (int i = 1; i < Pt && P[i] < n; i++) {
//        int pos = (int)(upper_bound(P+1, P+Pt, n - P[i]) - (P+1));
        while (pos > 0 && P[i] + P[pos] > n)
            pos--;
        if (pos >= i)
            ret--;
        ret += pos;
    }
    return ret/2;
}
int main() {
    sieve();
    int L, R;
    while (scanf("%d %d", &L, &R) == 2 && L+R) {
        R = R/2 * 2;
        L = (L-1)/2 * 2;
        printf("%lld\n", g(R) - g(L));
    }
    return 0;
}
/*
 10 20
 30 40
 0 0
 */