https://vjudge.net/problem/UVA-1635

题意:n个数,每相邻两个求和,最后变成1个数,问这个数除m的余数与第几个数无关

n个数使用次数分别为C(n-1,i) i∈[0,n-1]

对m分解质因数

同行内递推C(n-1,i),

累计答案的时候,只考虑C(n-1,i)分解质因数的结果  能否 将m的质因数 抵消

#include<cmath>
#include<cstring>
#include<cstdio>
#define N 100001
using namespace std;
int p[N],summ[N];
int ans[N];
int main()
{
int n,m,t,a,b,cnt;
while(scanf("%d%d",&n,&m)!=EOF)
{
p[0]=ans[0]=0;
memset(summ,0,sizeof(summ));
t=sqrt(m);
for(int i=2;i<=t;i++)
if(m%i==0)
{
p[++p[0]]=i;
while(m%i==0)
{
m/=i;
summ[p[0]]++;
}
}
if(m>1) p[++p[0]]=m,summ[p[0]]=1;
cnt=p[0];
for(int i=1;i<n-1;i++)
{
a=n-i; b=i;
for(int j=1;j<=p[0];j++)
{
if(a%p[j]==0)
{
while(a%p[j]==0)
{
a/=p[j];
summ[j]--;
if(!summ[j]) cnt--;
}
}
if(b%p[j]==0)
{
while(b%p[j]==0)
{
b/=p[j];
summ[j]++;
if(summ[j]==1) cnt++;
}
}
}
if(!cnt) ans[++ans[0]]=i+1;
}
printf("%d\n",ans[0]);
for(int i=1;i<ans[0];i++) printf("%d ",ans[i]);
if(ans[0]) printf("%d",ans[ans[0]]);
printf("\n");
}
}

  

最新文章

  1. W3School-CSS 表格实例
  2. PowerShell Start 1 - 使用Get - Help.
  3. storyBoard配置错误导致崩溃 superview]: unrecognized selector...
  4. 我的android学习经历28
  5. python使用random函数生成随机数
  6. ExtJs之 Ext.JSON
  7. nm和readelf命令的区别
  8. java.text.MessageFormat格式化字符串时的小技巧
  9. hdu 3345 War Chess
  10. 单例模式——Java EE设计模式解析与应用
  11. HDU1036 Average is not Fast Enough!
  12. VS2012 未找到与约束ContractName Microsoft.VisualStudio.Text.ITextDocumentFactoryService
  13. MySQL中的float和decimal类型有什么区别
  14. 电子产品使用感受之——我的Mac只有256GB,我的照片库该怎么办?
  15. PHP开发APP接口之返回数据
  16. Logstash读取Kafka数据写入HDFS详解
  17. java -server 和 -client 的不同,及 java -server 时抛错原因
  18. java判断给定路径或URL下的文件或文件夹是否存在?
  19. 处女座和小姐姐(三)-数位dp1.0
  20. Win8下IIS的安装和站点的公布

热门文章

  1. Zen Coding &amp;&amp; Emmet-Sublime 安装
  2. var,let,const,三种申明变量的整理
  3. StrBlob类——智能指针作为成员
  4. [git]基本用法1
  5. position定位-absolute与fixed
  6. FZU 1492 地震预测(链表)
  7. 【bzoj3545/bzoj3551】[ONTAK2010]Peaks/加强版 Kruskal+树上倍增+Dfs序+主席树
  8. 关于 [lambda x: x*i for i in range(4)] 理解
  9. AD高级培训PPT总结
  10. [洛谷P4512]【模板】多项式除法