首页 > 代码库 > UVA - 1635
UVA - 1635
这是一道组合数学加质因子分解的题目
题意 给n个数两两相邻的数互相相加,最后剩下一个数,然后看每个数的大小是否能%m
利用c(n,m)=(n-m+1)/m*c(n,m-1);
由于一直乘下去会long long ,所以只需(n-m+1)/m进行质数分解
#include<stdio.h> #include<string.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<string.h> #include<stdlib.h> #include<iostream> #include<algorithm> #include<string> #include<queue> #include<math.h> #include<map> using namespace std; #define MST(vis,x) memset(vis,x,sizeof(vis)) #define INF 0x3f3f3f3f #define ll long long #define ull unsigned long long #define maxn 100005 #define mod 1000000007 ll prim[maxn]; ll judge[1000005]; ll shu[1000005]; ll all; ll tempm[1000005]; ll ttempm[1000005]; ll tempall; void go(int x,int d) { for(int a=0; a<tempall; a++) { if(x==1)break; if(x%ttempm[a]==0) { if(x==1)break; while(x%ttempm[a]==0) { tempm[a]+=d; x/=ttempm[a]; } } } return ; } bool check() { for(int a=0;a<tempall;a++) if(tempm[a]>0)return false; return true; } int main() { MST(judge,0); all=0; int maxx=sqrt(1e9+0.5); for(int a=2; a<=maxx; a++) { if(!judge[a]) { judge[a]=1; shu[all++]=a; } for(int b=0; b<all&&shu[b]*a<=maxx; b++) { judge[shu[b]*a]=1; if(a%shu[b]==0)break; } } ll n,m; while(scanf("%lld%lld",&n,&m)!=EOF) { MST(tempm,0); tempall=0; for(int a=0; a<all; a++) { // printf("index %d\n",shu[a]); if(m==1)break; if(m%shu[a]==0) { if(m==1)break; while(m%shu[a]==0) { tempm[tempall]++; m/=shu[a]; } ttempm[tempall++]=shu[a]; } } if(m>1) { tempm[tempall]=1; ttempm[tempall++]=m; } int tempn=n; n--; ll sum=0; for(ll a=1; a<=n; a++) { go(n-a+1,-1); go(a,1); if(check()) prim[sum++]=a+1; } printf("%lld\n",sum); for(int a=0; a<sum; a++) { if(a==0)printf("%lld",prim[a]); else printf(" %lld",prim[a]); } printf("\n"); } return 0; }
UVA - 1635
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。