首页 > 代码库 > poj:2992 因子数量
poj:2992 因子数量
题意:
求 组合数c(n,k)的因子数量
由算术基本定理很容易求得,不过第一次却T了,加了好多预处理,o1查询,才过
#include <iostream>#include <stdio.h>#include<string.h>#include<algorithm>#include<string>#include<ctype.h>using namespace std;#define I64d lldint prime[100];int isnotprime[500];int fac[500][100];int nfac[500][100];long long ans[500][500];int np;void setprime(){ np=0; for(int i=2;i<=431;i++) { if(!isnotprime[i]) { prime[np++]=i; } for(int j=0;j<np&&i*prime[j]<=431;j++) { isnotprime[i*prime[j]]=1; if(i%prime[j]==0) break; } } return;}void setfac(){ memset(fac,0,sizeof(fac)); for(int i=2;i<=431;i++) { int p=i; for(int j=0;j<np;j++) { while(p%prime[j]==0) { fac[i][j]++; p/=prime[j]; } } } return;}void setans(){ memset(nfac,0,sizeof(nfac)); for(int i=2;i<=431;i++) { for(int j=0;j<np;j++) nfac[i][j]=nfac[i-1][j]+fac[i][j]; } for(int n=0;n<=431;n++) { for(int k=0;2*k<=n;k++) { long long res=1; for(int i=0;i<np;i++) { res*=nfac[n][i]-nfac[k][i]-nfac[n-k][i]+1; } ans[n][k]=ans[n][n-k]=res; } } return;}int main(){ setprime(); setfac(); setans(); int n,k; while(scanf("%d%d",&n,&k)!=EOF) { printf("%I64d\n",ans[n][k]); } return 0;}
poj:2992 因子数量
声明:以上内容来自用户投稿及互联网公开渠道收集整理发布,本网站不拥有所有权,未作人工编辑处理,也不承担相关法律责任,若内容有误或涉及侵权可进行投诉: 投诉/举报 工作人员会在5个工作日内联系你,一经查实,本站将立刻删除涉嫌侵权内容。