UVA1635 Irrelevant Elements —— 唯一分解定理 + 二项式定理

题目链接：https://vjudge.net/problem/UVA-1635

（紫书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的倍数，即此项与余数无关。

代码如下：

 #include <iostream>

 #include <cstdio>

 #include <cstring>

 #include <cstdlib>

 #include <string>

 #include <vector>

 #include <map>

 #include <set>

 #include <queue>

 #include <stack>

 #include <sstream>

 #include <algorithm>

 using namespace std;

 #define pb push_back

 #define mp make_pair

 #define ms(a, b)  memset((a), (b), sizeof(a))

 #define eps 0.0000001

 typedef long long LL;

 const int INF = 2e9;

 const LL LNF = 9e18;

 const int mod = 1e9+;

 const int maxn = 1e5+;

 int n, m, cnt;

 int fac[maxn], num_m[maxn], num_c[maxn];

 int ans[maxn], sum;

 void init()

 {

     n = n - ;    //题目从a[1]~a[n], 而二项式定理中， 从a[0]~a[n], 所以要与二项式定理中的n对应。

     ms(num_m, );

     ms(num_c, );

     cnt = ;

     int tmp = m;

     for(int i = ; i*i<=tmp; i++)

     {

         if(tmp%i==)

         {

             fac[++cnt] = i;

             while(tmp%i==) tmp /= i, num_m[cnt]++;

         }

     }

     if(tmp>) fac[++cnt] = tmp, num_m[cnt]++;

 }

 int test(int x)

 {

     int a = n-x+;

     int b = x;

     for(int i = ; i<=cnt; i++)

     {

         while(a%fac[i]==) num_c[i]++, a /= fac[i];

         while(b%fac[i]==) num_c[i]--, b /= fac[i];

     }

     for(int i = ; i<=cnt; i++)

         if(num_m[i]>num_c[i]) return ;

     return ;

 }

 void solve()

 {

     sum = ;

     for(int i = ; i<=n-; i++) //二项式的第0项和第n项都为1， 不需要考虑

         if(test(i))

             ans[++sum] = i+;   //二项式的第i项， 对应题目中的第i+1项

     printf("%d\n", sum);

     for(int i = ; i<=sum; i++)

         printf("%s%d", i==?"":" ", ans[i]);

     putchar('\n');

 }

 int main()

 {

     while(scanf("%d%d",&n, &m)!=EOF)

     {

         init();

         solve();

     }

 }

巴特西

UVA1635 Irrelevant Elements —— 唯一分解定理 + 二项式定理

最新文章

热门文章