题目
题目大意
对于给定的(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}), 不会涉及到高精度。
代码
#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
", countt);
for (register int i(0); i < countt; ++i){
printf(!i ? "%d" : " %d", pascal[i]);
}
putchar('
');
}
return 0;
}