首页 > 代码库 > Divisors_组合数因子个数
Divisors_组合数因子个数
Description
Your task in this problem is to determine the number of divisors of Cnk. Just for fun -- or do you need any special reason for such a useful computation?
Input
The input consists of several instances. Each instance consists of a single line containing two integers n and k (0 ≤ k ≤ n ≤ 431), separated by a single space.
Output
For each instance, output a line containing exactly one integer -- the number of distinct divisors of Cnk. For the input instances, this number does not exceed 263 - 1.
Sample Input
5 16 310 4
Sample Output
2616
【题意】求C(n,m)的质因子的个数。
【定理】设正整数n的所有素因子分解n=p1^a1*p2^a2*p3^a3****ps^as,那么T(n)=(a1+1)*(a2+1)*(a3+1)***(an+1);（求因子的个数的公式）
1.求出N以内素数
2.ei=[N/pi^1]+ [N/pi^2]+ …… + [N/pi^n] 其中[]为取整。即可以 int ei=0;while(N) ei+=(N/=pi);
3.套公式计算了，M=（e1+1）*（e2+1）*……*（en+1）
#include<iostream>#include<stdio.h>#include<string.h>using namespace std;const int N=450;int prime[1000]={2,3,5};int k=3;long long n,m,cnt[N][N];void get_prime()//将1000以内的素数存入prime数组；{ int flag; int p=2; for(int i=7;i<=1000;i+=p) { flag=0; p=6-p;//巧妙的跳过了3的倍数，提高了效率 for(int j=0;prime[j]*prime[j]<=i;j++) { if(i%prime[j]==0) { flag=1; break; } } if(!flag) prime[k++]=i; }}void init(){ memset(cnt,0,sizeof(cnt)); get_prime(); long long tmp,ret; for(int i=2;i<=431;i++) { for(int j=0;prime[j]<=i;j++) { tmp=i; ret=0; while(tmp) { tmp=tmp/prime[j]; ret+=tmp; } cnt[i][prime[j]]=ret;//i的质因子数 } }}int main(){ init(); long long ret,ans; while(~scanf("%lld%lld",&n,&m)) { ans=1; for(int i=0;prime[i]<=n;i++) { ret=cnt[n][prime[i]]-cnt[m][prime[i]]-cnt[n-m][prime[i]];//c(n,m)=n!/((n-m)!m!)，把对应因子个数相减，我们就得到了c(n,m)分解的结果 ans*=(ret+1); } printf("%lld\n",ans); } return 0;}
Divisors_组合数因子个数
声明：以上内容来自用户投稿及互联网公开渠道收集整理发布，本网站不拥有所有权，未作人工编辑处理，也不承担相关法律责任，若内容有误或涉及侵权可进行投诉： 投诉/举报 工作人员会在5个工作日内联系你，一经查实，本站将立刻删除涉嫌侵权内容。