POJ 2992 Divisors

这种题目，纯粹是折磨人的。那么容易TLE，昨天做了一个上午都没做出来，今天算是改对了，杨大哥说把素数打表，我嫌烦，不过打表之后确实会快。

每一个数都可以用 m = p1^a1 * p2^a2 * ...... * pn^an来表示，所以它的因子的个数有

(a1+1)*(a2+1)*...*(an + 1)中，很简单，每个因子都有指数都有0，1，2....到自身的ai+1个选择。

所以：我们要求出C( n, m )=n! /( ( n-m)! m! ),所以我们求出N! 的因子和它的指数，然后

ans = f[n]-f[n-m]-f[m]+1 其中 f[i] 就代表 i! 中的因子和它的指数。

素数打表时间花费相对这道题来说有点大。所以我尽量避免打表素数的个数。

代码：

#include<iostream>
using namespace std;
int f[510],p[510],len,a[510][510];
__int64 dp[510][510];
void Prime()
{
     int i,j;
     len=0;
     memset(f,0,sizeof(f));
     for( i=2;i*i<=500;i++){ //平方小于500的素数
          if( !f[i]){
              p[len++]=i;
              for( j=2*i;j*j<=500;j+=i)
                   f[j]=1;
          }
     }
}
void Solve()
{
     int i,j,n;
     memset(a,0,sizeof(a));
     for( i=2;i<=435;i++){
          for( j=0;j<i;j++)
               a[i][j]=a[i-1][j];
          n=i;
          for( j=0;j<len&&n>1;j++){
               while( n%p[j]==0){
                      a[i][p[j]]++;
                          n/=p[j];
                   }
          }
          if(n>1) a[i][n]++; //有大于p[len-1]*p[len-1] 的素数。
     }
}
int main()
{
    int i,j,sum,n,k;
    Prime();
    Solve();
   // freopen("prime.txt","w",stdout);
    memset(dp,0,sizeof(dp));
    while( scanf("%d%d",&n,&k)!=EOF){

           if(dp[n][k]){ printf("%I64d\n",dp[n][k]);continue;}

           __int64 sum=1;
           for( i=2;i<=n;i++)
                if( !f[i]) //是素数或者大于p[len-1]*p[len-1]
                    sum*=(a[n][i]-a[n-k][i]-a[k][i]+1);


           dp[n][k]=dp[n][n-k]=sum;
           printf("%I64d\n",sum);
    }
    return 0;
}

补充：软件开发 , C++ ,