360
技術社區[雲棲]
POJ 2992 質因子分解
題意要求出C(n,k)的因子個數 所以就需要把C(n,k)質因子分解 這題數據非常變態 我的思路沒問題但是無數次TLE之後我才發現應該先打出一個 n!的一個表 不然就超時 用C(n,k)=n!/(k!*(n-k)!) 這個公式就可以求出
#include <iostream>
#include<cstdio>
#include<cstring>
using namespace std;
#define max 435
int prime[max],nprime;
bool isprime[max];
void getprime()
{
long long i,j;
memset(isprime,1,sizeof(isprime));
isprime[1]=0;
nprime=0;
for(i=2; i<max; i++)
if(isprime[i])
{
prime[++nprime]=i;
for(j=i*i; j<max; j+=i)
isprime[j]=0;
}
}
long long a[435][435];
void getnum()
{
memset(a,0,sizeof(a));
for(int s=1; s<=431; s++)
{
int x=s;
memcpy(a[s],a[s-1],sizeof(a[s]));
if(isprime[x])
{
a[s][x]++;
continue;
}
for(int i=1; prime[i]<=x,x>1; i++)
while(x%prime[i]==0&&prime[i]>0)
{
a[s][prime[i]]++;
x/=prime[i];
}
}
}
int main()
{
getprime();
getnum();
int n,k;
long long ans;
while(~scanf("%d%d",&n,&k))
{
ans=1;
for(int i=2; i<=n; i++)
if(a[n][i]-a[k][i]-a[n-k][i])
ans*=(a[n][i]-a[k][i]-a[n-k][i]+1);
printf("%lld\n",ans);
}
return 0;
}
最後更新：2017-04-04 07:03:42