这是道有意思的题，在LRJ的杂题中有提到，题意是这样的：有n(n<=10^5)个数，每个数在[0,m), m <= 10^9中随机选一个数，对这n个数，做这样的操作，相邻的两个数求和后变成n-1个数，然后迭代到只剩下一个数，对这最后的数%m，问说哪个数是跟最后的数是没有影响的。
设这几个数是a,b,c,d->a+b,b+c,c+d->a+2b+c,b+2c+d->a+3b+3c+d，因此对于这n个数a1,a2,…,an，迭代到最后的ans=C(n-1,0)*a1+C(n-1,1)*a2+C(n-1,2)*a3+…+C(n-1,n-1)*an，因此当C(n-1,i)%m=0, i∈[0,n-1]的时候，ans对于该数是无关的。
因此，需要解决一个这样的问题，判断C(a, b)%m是否等于0，我们知道C(a, b)=a!/b!/(a-b)!，我们可以先筛出sqrt(m)以内的素数，复杂度O(sqrt(m))，然后把m进行质因数分解，复杂度O(logm)，然后把a!,b!,(a-b)!分别素因数(考虑m的素因数就可以了)分解，复杂度O(logm*logn)，然后判断，是否包含m的素因数就可以了，因此最后的复杂度为O(N*logm*logn)，代码如下：
#include <iostream> #include <string> #include <algorithm> #include <vector> #include <set> #include <stdio.h> #include <stdlib.h> #include <math.h> #include <string.h> #include <map> using namespace std; const int MAXN = 100005; const int MAXM = 1e9 + 5; //map<int, int> map_n[MAXN]; //N!质因数分解 int n, m; int s[MAXN]; vector<int> prime; void make_prime() { prime.clear(); memset(s, 0, sizeof(s)); //1...N之前的质数 //复杂度约等于N*lg(N) for(int i = 2; i < MAXN; i++) { if(s[i] == 0) { prime.push_back(i); for(int j = i + i; j < MAXN; j += i) s[j] = 1; } } } void go() { vector<map<int, int> > map_n; map<int, int> map_m; //M的分解 //分解M //复杂度lg(M) //初始化 map_m.clear(); int t_m = m; for(int i = 0; i < prime.size() && prime[i] <= sqrt(m * 1.0); i++) { int p = prime[i]; if(t_m % p == 0) { while(t_m % p == 0) { map_m[p]++; t_m /= p; } } } if(t_m != 1) map_m[t_m]++; //分解1...N的阶乘的质因数，这里其实只用分级M的质因数就可以了 //否则复杂度就是N*O(N)*lg(N)了，O(N)表示N之前的质数 //复杂度N*lg(M)*lg(N) map_n.clear(); map_n.resize(n + 1); for(int i = 0; i <= n; i++) { //初始化 //map_n[i].clear(); int j = i; //for(int k = 0; k < prime.size() && prime[k] <= j; k++) for(map<int, int>::iterator it = map_m.begin(); it != map_m.end(); it++) { int N = j, p = it->first; if(p > N) break; while(N) { map_n[i][p] += N / p; N /= p; } } } vector<int> ans; map<int, int>::iterator it; //复杂度为N*lg(M) //枚举解X //printf("count = %d\n", map_m.size()); for(int i = 0; i <= n; i++) { //枚举M的质因数 for(it = map_m.begin(); it != map_m.end(); it++) { int p = it->first; int cnt = it->second; if(map_n[n][p] - map_n[i][p] - map_n[n - i][p] < cnt) break; } if(it != map_m.end()) continue; ans.push_back(i + 1); } printf("%d\n", ans.size()); for(int i = 0; i < ans.size(); i++) { if(i == 0) printf("%d", ans[i]); else printf(" %d", ans[i]); //printf("%d ", ans[i]); } printf("\n"); } int main() { make_prime(); while(scanf("%d%d", &n, &m) != EOF) { --n; //求C(N, X)%M=0,X=[0, N],解X的个数 //ready(); //debug(); go(); } }转载于:https://www.cnblogs.com/litstrong/archive/2011/04/20/2022634.html
