本文共 1956 字，大约阅读时间需要 6 分钟。
题目链接：
（紫书320）
题解：
1.根据二项式定理， 可得递推公式： C(n,k) = (n-k+1)/k * C(n, k-1)
2.某一项与余数(%m)无关， 即表明该项的的系数是m的倍数， 由于 1<=n<=1e5, 直接运算的话肯定溢出。
所以 ：将数字进行分解质因数， 记录质因子以及其个数。由于题目只需判断某项的系数是否为m的倍数， 所以只需要考虑m所拥有的质因子。
3.fac[i]记录m的质因数， num_m[i]记录m的质因数fac[i]的个数， num_c[i]记录二项式系数（动态）的质因数fac[i]的个数。
4.对于所有的i， 如果num_c[i] >= num_m[i] 则表明此系数是m的倍数， 即此项与余数无关。
代码如下：
1 #include 2 #include 3 #include 4 #include 5 #include 6 #include 7 #include 8 #include 9 #include 10 #include 11 #include 12 #include 13 using namespace std;14 #define pb push_back15 #define mp make_pair16 #define ms(a, b) memset((a), (b), sizeof(a))17 #define eps 0.000000118 typedef long long LL;19 const int INF = 2e9;20 const LL LNF = 9e18;21 const int mod = 1e9+7;22 const int maxn = 1e5+10;23 24 int n, m, cnt;25 int fac[maxn], num_m[maxn], num_c[maxn];26 int ans[maxn], sum;27 28 void init()29 {30 n = n - 1; //题目从a[1]~a[n], 而二项式定理中， 从a[0]~a[n], 所以要与二项式定理中的n对应。31 ms(num_m, 0);32 ms(num_c, 0);33 cnt = 0;34 35 int tmp = m;36 for(int i = 2; i*i<=tmp; i++)37 {38 if(tmp%i==0)39 {40 fac[++cnt] = i;41 while(tmp%i==0) tmp /= i, num_m[cnt]++;42 }43 }44 if(tmp>1) fac[++cnt] = tmp, num_m[cnt]++;45 }46 47 int test(int x)48 {49 int a = n-x+1;50 int b = x;51 52 for(int i = 1; i<=cnt; i++)53 {54 while(a%fac[i]==0) num_c[i]++, a /= fac[i];55 while(b%fac[i]==0) num_c[i]--, b /= fac[i];56 }57 58 for(int i = 1; i<=cnt; i++)59 if(num_m[i]>num_c[i]) return 0;60 return 1;61 }62 63 void solve()64 {65 sum = 0;66 for(int i = 1; i<=n-1; i++) //二项式的第0项和第n项都为1， 不需要考虑67 if(test(i))68 ans[++sum] = i+1; //二项式的第i项， 对应题目中的第i+1项69 70 printf("%d\n", sum);71 for(int i = 1; i<=sum; i++)72 printf("%s%d", i==1?"":" ", ans[i]);73 putchar('\n');74 }75 76 int main()77 {78 while(scanf("%d%d",&n, &m)!=EOF)79 {80 init();81 solve();82 }83 }
转载于:https://www.cnblogs.com/DOLFAMINGO/p/7538687.html
