UVa 1635 无关的元素（唯一分解定理+二项式定理）

题意：

给定n个数a1，a2，...an,依次求出相邻两数之和，将得到一个新数列。重复上述操作，最后结果将变成一个数。问这个数除以m的余数与哪些数无关？例如n=3，m=2时，第一次求和得到a1+a2，a2+a3，再求和得到a1+2a2+a3，它除以2的余数和a2无关。

思路：

如果有n个数，最后结果就是杨辉三角的第n-1行。这样算出每一项的系数是很容易的，但是n很大，系数到最后很大。所以直接C%m的话不行。

有个整除的条件：m中每个素因子在C中都存在并且C中的指数大于等于m的素因子的指数。

所以我们先将m分解素因子，依次计算各个素因子在C中的指数，这里还要用到递推式，每次从左到右计算C的时候，只需要考虑（n-k+1）/k,因为在上一次已经计算过了，它的素因子指数已经保存下来了。

 #include<iostream>

 #include<cstdio>

 #include<cmath>

 #include<cstring>

 using namespace std;

 const int maxn=1e5+;

 int n,m;

 int fac[][];  //f[][0]用来存储质因子，f[][1]存储对应质因子的个数

 int c[];

 int a[maxn];

 int num;   //m分解质因子的个数

 void factor()   //分解质因子

 {

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

     {

         if(m%i==)

         {

             fac[++num][]=i;

             fac[num][]=;

             do

             {

                 fac[num][]++;

                 m/=i;

             }while(m%i==);

         }

     }

     if(m>)

     {

         fac[++num][]=m;

         fac[num][]=;

     }

 }

 bool check(int n,int i)

 {

     int x=n-i;  //n-1-i+1

     int y=i;

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

     {

         int p=fac[i][];

         while(x%p==)

         {

             x/=p;

             c[i]++;

         }

         while(y%p==)

         {

             y/=p;

             c[i]--;

         }

     }

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

         if(c[i]<fac[i][])

             return false;

     return true;

 }

 int main()

 {

     while(cin>>n>>m)

     {

         num=;

         int cnt=;

         factor();

         memset(c,,sizeof(c));

         for(int i=;i<n-;i++)   //第1项和最后一项都是1，直接跳过

         {

             if(check(n,i))

                 a[cnt++]=i+;

         }

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

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

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

         printf("\n");

     }

     return ;

 }

巴特西

UVa 1635 无关的元素（唯一分解定理+二项式定理）

最新文章

热门文章