金融网站建设/成功的营销案例及分析

题目链接：点击打开链接

题意：给定n个数a1,a2····an,依次求出相邻两个数值和，将得到一个新数列，重复上述操作，最后结果将变为一个数，问这个数除以m的余数与那些数无关？例如n=3,m=2时，第一次得到a1+a2,a2+a3，在求和得到a1+2*a2+a3，它除以2的余数和a2无关。1=<n<=10^5, 2=<m<=10^9

解题思路：

1、首先我们可以发现对于给定的n其实每项的系数就是C(n-1,i-1)，所以我们只需要找到每项的系数对m取余是否为0即可

2、由于m的取值范围为10^9,所以我们只需要筛选 √(10^9)的素数，然后对m进行分解；如果分解后m>1，说明当前m的是原m的一个素数，而且m> √(10^9)，因此我们只需记录它即可

3、根据C(n,k)=C(n,k)*(n-i+1)/i;(根据这个公式我们可以发现C(n,k)*(n-i+1)一定能整除i)，对m分解式中的素数进行操作即可，具体见代码

#include <cstdio>
#include <cstring>
#include <cmath>
using namespace std;const int maxn= 32000;
int prime[maxn+1];
int nprime;
void getPrime()
{int m=sqrt(maxn+0.5);for(int i=2; i<=m; ++i) if(!prime[i])for(int j=i*i; j<=maxn; j+=i) prime[j]=1;nprime=0;for(int i=2; i<=maxn; ++i){if(!prime[i])prime[nprime++]=i;}
}
int n,m;
int pm[20];
int em[20];
int im;
void init()
{memset(pm,0,sizeof(pm));memset(em,0,sizeof(em));im=0;for(int i=0; i<nprime&&m>=prime[i]; i++){if(m%prime[i]==0){pm[im]=prime[i];while((m%prime[i]==0)&&(m/=prime[i]))em[im]++;im++;}if(n==0||n==1)break;}if(m>1){pm[im]=m;em[im]=1;im++;}
}
bool getFactors(int x,int y)
{bool ff=true;for(int i=0; i<im; ++i){while((x%pm[i]==0)&&(x/=pm[i]))em[i]--;while(y%pm[i]==0&&(y/=pm[i]))em[i]++;if(em[i]>0)ff=false;}return ff;
}
bool flag[100010];
int main()
{getPrime();while(scanf("%d%d",&n,&m)!=EOF){init();memset(flag,false,sizeof(flag));int ans=0;int ends=0;for(int i=1; i<=n; ++i)if(getFactors(n-i,i)){flag[i+1]=true;ans++;ends=i+1;}printf("%d\n",ans);if(ans!=0){for(int i=1; i<ends; i++)if(flag[i])printf("%d ",i);printf("%d",ends);}printf("\n");}return 0;
}

每个整数的唯一分解式项数不多（long long 类型的数值最多20项，前21个素数相乘long long就溢出了）