解題區/解題區 - UVa

UVa 1635 - Irrelevant Elements

contents

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

Problem

題目給定一種亂數產生方式，一開始先給定 n 個數字序列 ai (1 <= i <= n)，之後相鄰兩兩相加得到 n - 1 個數字的序列，最後這一個數字 mod m = ? 來決定最後要輸出的亂數。

請問最後產生出來的數字 無關序列的第幾項。

Sample Input

1
3 2

Sample Output

1
2
1
2

Solution

其實可以見到的，第 i 個數字會在最後使用 C(n-1, i) 次，無關的意思，也就是說恰好 C(n-1, i) == 0 mod m，不管 ai 為何皆不影響最後產生出來的數字。

為了加速運算，我們必須先質因數分解 m 的結果。

對於 C(a, b) = a! / (b!(b-a)!) 是否整除 m，查閱 m 的所有質因數 p 的個數是否符合需求。

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
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
#include <stdio.h>
#include <math.h>
#include <iostream>
#include <algorithm>
#include <vector>
#include <queue>
#include <stack>
#include <set>
#include <string.h>
#include <assert.h>
using namespace std;
#define maxL (50000>>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[5500], Pt = 0;
void sieve() {
    register int i, j, k, l;
    SET(1);
    int n = 50000;
    for(i = 2; i <= n; i++) {
        if(!GET(i)) {
            for(j = i + i; j <= n; j += i)
                SET(j);
            P[Pt++] = i;
        }
    }
}
int isPrime(int n) {
    for(int i = 0; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            return 0;
        }
    }
    return 1;
}
vector< pair<int, int> > factor(int n) {
    vector< pair<int, int> > R;
    
    for(int i = 0, j; i < Pt && P[i] * P[i] <= n; i++) {
        if(n%P[i] == 0) {
            for(j = 0; n%P[i] == 0; n /= P[i], j++);
            R.push_back(make_pair(P[i], j));
        }
    }
    if(n != 1)	R.push_back(make_pair(n, 1));
    return R;
}
int g(int n, int p) {
    int ret = 0;
    long long pp = p;
    while (n >= pp) {
        ret += n / pp;
        pp *= p;
    }
    return ret;
}
int main() {
    sieve();
    int n, m;
    while (scanf("%d %d", &n, &m) == 2) {
        vector< pair<int, int> > f = factor(m);
        vector<int> solution;
        n--;
        for (int i = 0; i <= n; i++) {
            int ok = 1;
            for (int j = 0; j < f.size() && ok; j++) {
                int p = f[j].first;
                int cnt = g(n, p) - g(i, p) - g(n - i, p); // C(n, i) has p^cnt.
                if (cnt < f[j].second) {
                    ok = 0;
                }
            }
            if (ok) {
                solution.push_back(i + 1);
            }
        }
        printf("%d\n", (int)solution.size());
        for (int i = 0; i < solution.size(); i++) {
            printf("%d%s", solution[i], i == solution.size() - 1 ? "" : " ");
        }
        puts("");
    }
    return 0;
}