Irrelevant Elements, ACM/ICPC NEERC 2004, UVa1635

这种题目最重要的是思路了清晰

 1 #include <cstdio>
 2 #include <cstring>
 3 const int maxn = 100005;//sqrt(n)+1 is enough
 4
 5 int fac[100][2];
 6 int fac_c[100];
 7 int a[maxn];
 8 void factor(int m) {
 9     int& num = fac[0][0];
10     num = 0;
11     for (int i = 2; i*i <= m; i++) {
12         if(m%i == 0) {
13             fac[++num][0] = i;
14             fac[num][1] = 0;
15             do {
16                 fac[num][1]++;
17                 m/= i;
18             } while(m%i == 0);
19         }
20     }
21     if (m > 1) {
22         fac[++num][0] = m;
23         fac[num][1] = 1;
24     }
25 }
26 bool check(int n, int j) {
27     int num = fac[0][0];
28     int a = n - j;
29     int b = j;
30     for (int i = 1; i <= num; i++) {
31         //为了提高效率，只用检验m的分解式中的素因数
32         int p = fac[i][0];
33         int& q = fac_c[i];
34         for (; a%p == 0; a/=p, q++);
35         for (; b%p == 0; b/=p, q--);
36     }
37     for (int i = 1; i <= num; i++) {
38         if (fac[i][1] > fac_c[i]) {
39             return false;
40         }
41     }
42     return true;
43 }
44 int main(void) {
45     int n, m;
46     for (; scanf("%d%d", &n, &m)==2;printf("\n")) {
47         int cnt = 0;
48         factor(m);
49         memset(fac_c, 0, sizeof(fac_c));
50         for (int i = 1; i < n; i++) {
51             if (check(n, i)) {
52                 a[cnt++] = i+1;
53             }
54         }
55         printf("%d\n", cnt);
56         for (int i = 0; i < cnt; i++) {
57             printf("%s%d",i==0?"":" ", a[i]);
58         }
59     }
60     return 0;
61 }

View Code