首页 > 代码库 > 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 因子数量