题意:

给定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

解法:

将所有的加法过程列出来可以得到,n个数合并成1个数需要n-1步,且最后的表达式写成初始项相加的形式 每一项的系数恰好就是一个二项式系数。

问除以m的余数与那些数无关,其实就是问这些因子中哪些是m的倍数。我们还是用分解m质因子的方法,将m的质因子全部先分解出来,然后遍历每个二项式系数,看他们能否整除这些质因子(如果这个二项式系数改写成质因子的幂次形式,的这个幂小于m中的这个幂,就不行) 。

除此之外还要学习的就是怎么计算这个幂次,尤其是被除数为分数的时候,分子的幂次的贡献为正,分母为负

 #include<cstdio>
#include<vector>
#include<cstring>
using namespace std;
int vis[ + ]; int work_quality_factor(int n, int quality_fac[], int frequency[])
{//n是待分解的数,quality_fac[]会存放它包含的质因子,而frequency[]存放对应次数
//如q_f[k]=7,fre[k]=2就表示质因数分解后里面包含有7,且次数是2
//函数返回有几种质因子,比如分解了25就返回1,分解28返回2
int res, temp, i;
res = ;
temp = n;
for (i = ; i*i <= temp; i++)
if (temp%i == )
{
quality_fac[res] = i;
frequency[res] = ;
while (temp%i == )
{
temp = temp / i;
frequency[res]++;
}
res++;
}
if (temp > )
{
quality_fac[res] = temp;
frequency[res++] = ;
}
return res;
} int main() {
int n, m;
while (scanf("%d%d", &n, &m) != EOF) {
n--;
memset(vis, , sizeof(vis));
int fac[], frq[];
int primenum = work_quality_factor(m, fac, frq); for (int i = ; i < primenum; i++) {
int min_e = frq[i], x, e = ;
// c(n,k)=c(n,k-1)*(n-k+1)/k
for (int k = ; k < n; k++) {
//分成上下两部分除,上面的幂次的贡献为正,下面为负
x = n - k + ;
while (x%fac[i]==) { x /= fac[i]; e++; }
x = k;
while (x%fac[i]==) { x /= fac[i]; e--; }
if (e < min_e)vis[k] = ;
}
} vector<int>ans;
for (int i = ; i < n; i++)
if (!vis[i])ans.push_back(i + );
printf("%d\n", ans.size());
if (!ans.empty()) {
printf("%d", ans[]);
for (int i = ; i < ans.size(); i++)
printf(" %d", ans[i]);
}
printf("\n");
}
return ;
}

最新文章

  1. Bzoj 1336&amp;1337 Alien最小圆覆盖
  2. OC内存管理--zombie对象
  3. django-CSRF verification failed. Request aborted
  4. ugui自制摇杆。
  5. Quiz 6a Question 7————An Introduction to Interactive Programming in Python
  6. CAN总线基础
  7. Object-c学习之路三(@class与#import的区别)
  8. sealed的作用
  9. Javascript设计模式(1)
  10. H3C交换机如何配置管理VLAN
  11. python之动态参数 *args,**kwargs和命名空间
  12. spring boot 使用第三方jar的方法
  13. 移动UI布局设计原则(一)
  14. Ring0创建事件Ring3设置事件
  15. js记录用户访问页面和停留时间
  16. Oracle常用命令-用户、表空间、赋权限、导入导出
  17. C#进行数据筛选(二)
  18. Hyperscan 介绍与安装【转】
  19. PHP代码执行函数总结
  20. hdu 2105:The Center of Gravity(计算几何,求三角形重心)

热门文章

  1. 视觉slam十四讲第七章课后习题6
  2. 快速理解YOLO目标检测
  3. Codeforces_446_B
  4. ArrayList 并发操作 ConcurrentModificationException 异常
  5. 一个新实验:使用gRPC-Web从浏览器调用.NET gRPC服务
  6. Go语言实现:【剑指offer】替换空格
  7. rabbitmq在kubernetes中持久化集群部署
  8. react-native当使用antd-mobile出现View config not found for name div
  9. jq根据table的tr行数动态删除相应的行
  10. Ts环境搭建