首页 > 代码库 > UVa 1635 无关的元素（唯一分解定理+二项式定理）
UVa 1635 无关的元素（唯一分解定理+二项式定理）
https://vjudge.net/problem/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,因为
在上一次已经计算过了，它的素因子指数已经保存下来了。
1 #include<iostream> 2 #include<cstdio> 3 #include<cmath> 4 #include<cstring> 5 using namespace std; 6 7 const int maxn=1e5+5; 8 9 int n,m;10 int fac[105][2]; //f[][0]用来存储质因子，f[][1]存储对应质因子的个数11 int c[105];12 int a[maxn];13 int num; //m分解质因子的个数14 15 void factor() //分解质因子16 {17 for(int i=2;i*i<=m;i++)18 {19 if(m%i==0)20 {21 fac[++num][0]=i;22 fac[num][1]=0;23 do24 {25 fac[num][1]++;26 m/=i;27 }while(m%i==0);28 }29 }30 if(m>1)31 {32 fac[++num][0]=m;33 fac[num][1]=1;34 }35 }36 37 bool check(int n,int i)38 {39 int x=n-i; //n-1-i+140 int y=i;41 for(int i=1;i<=num;i++)42 {43 int p=fac[i][0];44 while(x%p==0)45 {46 x/=p;47 c[i]++;48 }49 while(y%p==0)50 {51 y/=p;52 c[i]--;53 }54 }55 for(int i=1;i<=num;i++)56 if(c[i]<fac[i][1])57 return false;58 return true;59 }60 61 int main()62 {63 while(cin>>n>>m)64 {65 num=0;66 int cnt=0;67 factor();68 memset(c,0,sizeof(c));69 for(int i=1;i<n-1;i++) //第1项和最后一项都是1，直接跳过70 {71 if(check(n,i))72 a[cnt++]=i+1;73 }74 printf("%d\n",cnt);75 for (int i = 0; i < cnt; i++)76 printf("%s%d", i == 0 ? "" : " ", a[i]);77 printf("\n");78 }79 return 0;80 }
UVa 1635 无关的元素（唯一分解定理+二项式定理）
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。