题意:

求 组合数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 lld
int prime[];
int isnotprime[];
int fac[][];
int nfac[][];
long long ans[][];
int np;
void setprime()
{
np=;
for(int i=;i<=;i++)
{
if(!isnotprime[i])
{
prime[np++]=i;
}
for(int j=;j<np&&i*prime[j]<=;j++)
{
isnotprime[i*prime[j]]=;
if(i%prime[j]==)
break;
}
}
return;
}
void setfac()
{
memset(fac,,sizeof(fac));
for(int i=;i<=;i++)
{
int p=i;
for(int j=;j<np;j++)
{
while(p%prime[j]==)
{
fac[i][j]++;
p/=prime[j];
}
}
}
return;
}
void setans()
{
memset(nfac,,sizeof(nfac));
for(int i=;i<=;i++)
{
for(int j=;j<np;j++)
nfac[i][j]=nfac[i-][j]+fac[i][j];
}
for(int n=;n<=;n++)
{
for(int k=;*k<=n;k++)
{
long long res=;
for(int i=;i<np;i++)
{
res*=nfac[n][i]-nfac[k][i]-nfac[n-k][i]+;
}
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 ;
}
05-11 11:16