题目
题目大意
对于给定的\(n\)个数\(a_1\), \(a_2\), ···, \(a_n\), 依次求出相邻两数之和,
将得到一个新数列。重复上述操作, 最后结果将变成一个数。问这个数除以\(m\)的余数将与哪些数无关? 例如\(n = 3\), \(m =
2\)时, 第一次求和得到\(a_1 +
a_2\), \(a_2 + a_3\),
再求和得到\(a_1 + 2a_2 + a_3\),
它除以\(2\)的余数和\(a_2\)无关。\(1 ≤
n ≤ 10^5\), \(2 ≤ m ≤
10^9\)。
题解
通过一些打表我们发现, 在一般情况下, 最后\(a_i\)的系数是\(C_{n - 1}^{i - 1}\)。例如\(n = 5\)时最后结果是\(a_1 + 4a_2 + 6a_3 + 4a_4 +
a_5\)。这样问题就变成了\(C_{n -
1}^{0}\), \(C_{n - 1}^{1}\),
···, \(C_{n - 1}^{n -
1}\)中有哪些是\(m\)的倍数。
由此我们可以递推出所有\(C_{n - 1}^{i -
1}\), 但其中一部分太过巨大,
需要使用高精度。但此问题只关心那些是\(m\)的倍数,
于是又可以用到唯一分解定理。并且递推可以使用\(C_n^k = \frac{n - k + 1}{k}C_n^{k - 1}\),
不会涉及到高精度。
代码
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
| #include<cstdio>
#include<cstring>
int n, m;
int factors[110][2], ccount[110], pascal[100010], num;
inline bool Judge(const int &n, const int &factor) {
register int x(n - factor), y(factor);
for (register int i(1), p; i <= num; ++i) {
p = factors[i][0];
while (!(x % p)) {
x /= p;
++ccount[i];
}
while (!(y % p)) {
y /= p;
--ccount[i];
}
}
for (register int i(1); i <= num; ++i) {
if (ccount[i] < factors[i][1]) {
return false;
}
}
return true;
}
int main(int argc, char const *argv[]) {
while (~scanf("%d %d", &n, &m)) {
register int countt((num = 0));
for (register int i(2); i * i <= m; ++i) {
if (!(m % i)) {
factors[++num][0] = i;
factors[num][1] = 0;
do {
++factors[num][1];
m /= i;
} while(!(m % i));
}
}
if (m > 1) {
factors[++num][0] = m;
factors[num][1] = 1;
}
memset(ccount, 0, sizeof(ccount));
for (register int i(1); i < n - 1; ++i) {
if (Judge(n, i)) {
pascal[countt++] = i + 1;
}
}
printf("%d\n", countt);
for (register int i(0); i < countt; ++i){
printf(!i ? "%d" : " %d", pascal[i]);
}
putchar('\n');
}
return 0;
}
|