首页 > 代码库 > URAL 1091. Tmutarakan Exams(容斥原理)
URAL 1091. Tmutarakan Exams(容斥原理)
题目链接
题意 : 给你两个数k,s,让你找k个数,这k个数都不大于s,并且这k个数的公约数大于1。
思路 : 枚举一下素数倍数,求组合数,最后容斥原理求最终结果。
当k=3,s=20的时候 :
2 : 2 4 6 8 10 12 14 16 18 20
3 :3 6 9 12 15 18
5 :5 10 15 20
只要从每个集合里边找出k个即可,这就是用组合数了。但是会有重复的,例如
2 : 6 12 18
3 : 6 12 18
这样就多加了一个,要再减去,所以就是容斥原理。加一个的减两个的,但是因为素数的乘积中,最小的就是2*3*5=30 ,要是k也最小为2的话,也就是30 60 ,这样已经超范围了,所以不用加三个减四个的了。
而重复的也就是 2 * 3 2 * 5 2 * 7 3 * 5 3 * 7 2 * 11这些,所以倒是不用循环枚举了,直接减也可以
1 #include <stdio.h> 2 #include <string.h> 3 #include <iostream> 4 5 using namespace std ; 6 7 const int prime[]={2,3,5,7,11,13,17,19,23,29} ; 8 int c[51][51] ; 9 10 void com()11 {12 memset(c,0,sizeof(c)) ;13 for(int i = 0 ; i < 51 ; i++)14 c[i][0] = c[i][i] = 1 ;15 for(int i = 1 ; i < 51 ; i++){16 for(int j = 1 ; j < i ; j++)17 c[i][j] = c[i-1][j]+c[i-1][j-1] ;18 }19 }20 int main()21 {22 int k,s ;23 com();24 while(~scanf("%d %d",&k,&s)){25 int ans = 0 ;26 27 for(int i = 0 ; i < 10 ; i++)28 {29 if(s / prime[i] >= k)30 ans += c[s/prime[i]][k] ;31 //printf("%d\n",c[s/prime[i]][k]);32 }33 ans -= c[s/6][k] ;34 ans -= c[s/10][k] ;35 ans -= c[s/14][k] ;36 ans -= c[s/22][k] ;37 ans -= c[s/15][k] ;38 ans -= c[s/21][k] ;39 if(ans > 10000)40 ans = 10000 ;41 printf("%d\n",ans) ;42 }43 return 0 ;44 }
URAL 1091. Tmutarakan Exams(容斥原理)
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。