UVA 1635 Irrelevant Elements
2024-08-30 23:07:03
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");
}
}
最新文章
- W3School-CSS 表格实例
- PowerShell Start 1 - 使用Get - Help.
- storyBoard配置错误导致崩溃 superview]: unrecognized selector...
- 我的android学习经历28
- python使用random函数生成随机数
- ExtJs之 Ext.JSON
- nm和readelf命令的区别
- java.text.MessageFormat格式化字符串时的小技巧
- hdu 3345 War Chess
- 单例模式——Java EE设计模式解析与应用
- HDU1036 Average is not Fast Enough!
- VS2012 未找到与约束ContractName Microsoft.VisualStudio.Text.ITextDocumentFactoryService
- MySQL中的float和decimal类型有什么区别
- 电子产品使用感受之——我的Mac只有256GB,我的照片库该怎么办?
- PHP开发APP接口之返回数据
- Logstash读取Kafka数据写入HDFS详解
- java -server 和 -client 的不同,及 java -server 时抛错原因
- java判断给定路径或URL下的文件或文件夹是否存在?
- 处女座和小姐姐(三)-数位dp1.0
- Win8下IIS的安装和站点的公布
热门文章
- Zen Coding &;&; Emmet-Sublime 安装
- var,let,const,三种申明变量的整理
- StrBlob类——智能指针作为成员
- [git]基本用法1
- position定位-absolute与fixed
- FZU 1492 地震预测(链表)
- 【bzoj3545/bzoj3551】[ONTAK2010]Peaks/加强版 Kruskal+树上倍增+Dfs序+主席树
- 关于 [lambda x: x*i for i in range(4)] 理解
- AD高级培训PPT总结
- [洛谷P4512]【模板】多项式除法