解題區/解題區 - Zerojudge

a994. 10325 - The Lottery

contents

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

Problem

模擬計算，刪除組合數字的倍數，請問剩下多少個數字可選。

Sample Input

1
2
3
4
5
6
10 2
2 3
20 2
2 4
100 3
3 5 7

Sample Output

1
2
3
3
10
45

Solution

這一題是非常容易的題目，利用排容原理可以在 $O(2^m)$ 的時間內完成，所以複雜度沒有太大的改善，若使用 bitmask 的方式撰寫，複雜度會落在 $O(m \times 2^m)$，中間會有大量的 gcd(a, b) 計算，歐基里德輾轉相除法的常數並不大，時間複雜度 $O(\log n)$。

為了加速運算，可以利用組合來完成，利用選用組合 1011，可以得到 lcm(1011) = lcm(lcm(1010), A[0]) 完成，因此只會有 $O(2^m)$ 次 gcd() 的成本，整整少了常數 m。

因此需要使用 lowbit = i&(-i) 的位元運算技巧，同時為了得到 2 的冪次的次方數，建議使用內置函數 __builtin 系列，編譯器最佳化計算。而 gcd 使用，也使用內建的 __gcd(a, b) 但內置函數通常只會設置在 unsigned int 意即 32-bits 無號整數，要防止運算 overflow。

有人會提案使用建表，這樣查找只需要 $O(1)$，但記憶體置換會造成負擔，有兩個 $O(2^{15})$ 的 cache page，而且還要前置建表的計算成本。根據實驗測試，建表的方案速度會比較慢。

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
#include <bits/stdc++.h>
using namespace std;
int main() {
    int n, m, A[16];
    unsigned int dp[1<<15], a, b;
    while (scanf("%d %d", &n, &m) == 2) {
        for (int i = 1; i <= m; i++)
            scanf("%d", &A[i]);
        int ret = n;
        dp[0] = 1;
        for (int i = 1; i < (1<<m); i++) {
            long long val;
            a = dp[i-(i&(-i))], b = A[__builtin_ffs(i&(-i))];
            if (a > n) {dp[i] = n+1; continue;}
            val = b / __gcd(a, b) * (long long) a;
            if (val <= n) {
                dp[i] = val;
                if (__builtin_popcount(i)&1)
                    ret -= n / val;
                else
                    ret += n / val;
            } else {
                dp[i] = n+1;
            }
        }
        
        printf("%d\n", ret);
    }
    return 0;
}