首页 > 代码库 > 组合数学部分知识点
组合数学部分知识点
数学
1.质数,log,二分,题设证明
2.容斥原理 错排公式
3.与一个数a互质,必然是c+ka,c为a以内与a 互质的数字。Happy 2006
4.对于任意的整数n,必然存在一个由不多于两个的数来组成的一个倍数。因为a,aa,aaa……取n+1个,则必有两个模n余数相同,相减即得n的倍数m。而m只由a、0组成。5.对于大的数字,一般用同模定理缩减规模 (a+b)%m=a%m+b%m,(a*b)%m=a%m*b%m
组合数学
加法乘法原理 分类,分步
错排公式 D(n) = (n-1) [D(n-2) + D(n-1)]
第一步,把第n个元素放在一个位置,比如位置k,一共有n-1种方法;
第二步,放编号为k的元素,这时有两种情况:⑴把它放到位置n,那么,对于剩下的n-1个元素,由于第k个元素放到了位置n,剩下n-2个元素就有D(n-2)种方法;⑵第k个元素不把它放到位置n,这时,对于这n-1个元素,有D(n-1)种方法;
/* Sky Code求得是n个数中,有多少组(a,b,c,d)的公约数为1,值得注意的是这四个数不一定两两互质。 所以我们从它的反面考虑,先求出公约数不为1的个数。 思路:把每个数素数分解,记录不重复素因子所能组成的因子,把这些因子的总数统计,并且统计每个因子是由多少个素因子组成 如这n个数中含2的个数为a,含3的个数为b,含6的个数为c,那么公约数大于1的总数为p=c(a,4)+c(b,4)-c(c,4),总的个数为c(n,4) 用c(n,4)-p即为所求 */ #include <stdio.h> #include <string.h> #include <stdlib.h> #define MAXN 10000+100 __int64 A[MAXN]; __int64 B[MAXN]; __int64 C[MAXN]; __int64 P[MAXN]; __int64 N; __int64 num; __int64 yz; void dfs() { __int64 i,j; __int64 temp,k; yz=0; for(i=2;i*i<=num;i++) { if(num%i==0) { C[yz++]=i; while(num%i==0) num/=i; } } if(num>1) C[yz++]=num;//C中存放质因子 for(i=1;i<(1<<yz);i++) { k=0;temp=1;//排列组合所有质因子,组合成的因子。每一位代表一个因子的C中下标 for(j=0;j<yz;j++) if(i&(1<<j))//判断有哪位就相乘 { k++; temp*=C[j]; } B[temp]++;//记录这个因子有多少个 A[temp]=k;//记录这个因子由几个质因子组成 } } int main() { __int64 i; __int64 ans; memset(P,0,sizeof(A)); for(i=4;i<MAXN;i++) { P[i]=i*(i-1)*(i-2)*(i-3)/24; } while(scanf("%d",&N)!=EOF) { memset(B,0,sizeof(A)); for(i=0;i<N;i++) { scanf("%d",&num); dfs(); } ans=0; for(i=2;i<MAXN;i++) if(B[i])//容斥原理,奇相加。偶相减 { if(A[i]%2) ans+=P[B[i]]; else ans-=P[B[i]]; } ans=P[N]-ans; printf("%I64d\n",ans); } return 0; }
组合数学部分知识点
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。