首页 > 代码库 > poj 2992 Divisors
poj 2992 Divisors
题目链接:http://poj.org/problem?id=2992
题目大意:就是叫你求组合数C(n,m)的因子的个数。
思路:求解这题需要用到以下几个定理
1、对任意的n,可以这么表示 n=p1^e1*p2^e2*p3*e3*......pn^en 。(p1,p2,p3......pn都为素数)
2、对任意的n的因子数为:(1+e1)*(1+e2)*(1+e3)*......*(1+en)
3、n!的素数因子=(n-1)!的素数因子+n的素数因子
4、C(n,k)的素因子=n!的素因子 - (n-k)!的素因子 - k!的素因子
有了上面介绍的几个定理那么这题就比较好解啦。。。。
code:
#include<cstdio> #include<iostream> #include<cmath> #include<cstring> #include<algorithm> using namespace std; int a[450][450],b[450]; //a[i][j] 表示 i!中的素因子j的出现的次数 int prime[450],vis[450]; int len; int primetable() //打印素数表 { int i,j; int c=0; memset(vis,0,sizeof(vis)); for(i=2;i<=431;i++) { if(!vis[i]) { prime[c++]=i; for(j=i*i;j<=431;j+=i) { vis[j]=1; } } } return c; } void f() //计算2!到431!中的每个数中的素因子的出现的次数 { int i,j; memset(a,0,sizeof(a)); for(i=2;i<=431;i++) { int ii=i; memcpy(a[i],a[i-1],sizeof(a[i])); //把a[i-1]中的各元素拷贝到a[i]中 for(j=0;j<len;j++) { if(prime[j]>ii) break; if(ii%prime[j]==0) { int sum=0; while(ii%prime[j]==0) { sum++; ii/=prime[j]; } a[i][prime[j]]+=sum; } } } } int main() { int n,k,i,j; len=primetable(); f(); while(scanf("%d%d",&n,&k)==2) { memcpy(b,a[n],sizeof(a[n])); __int64 cnt=1; //cnt用__int64,其他的变量用int就行啦 for(i=0;i<=431;i++) { b[i]=b[i]-a[k][i]-a[n-k][i]; cnt*=(1+b[i]); } printf("%I64d\n",cnt); } return 0; }
poj 2992 Divisors
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。