POJ 2992 - Divisors

http://poj.org/problem?id=2992

概要

C(n,k) の約数の数を答える．

制約

解法

しばらく TLE から抜け出せず，Problems Statement: CTU Open 2005 Contest からインプットをとってきてみると，93528行もあった…

n! が素因数として p を f(n,p) 個持っているとすると，C(n,k) は p を素因数として f(n,p) - f(k,p) - f(n-k,p) 個持っている． これをすべての素数 p に関して計算して，1を足したものの積をとれば C(n,k) の約数が求まる．

f(n,p) は，n を p^i (i = 1, 2, ...) で割ったときの商の和をとることで計算できる．

この f(n,p) を毎回計算しても TLE するので，n, p でメモ化するか，下のように予め計算してテーブルを作っておくとやっと通るようになった (610MS)．

しかし，なぜかこのゴルフしたコードのほうがかなり速かった (235MS)．

p[431],s[999],t[432][432],*q=p,j,N,K;long long a;main(i){for(i=2;i<432;i++)if(!s[i])for(*q++=j=i;j<432;s[j+=i]=1);for(i=0;i<432;i++)for(q=p;*q;q++)for(j=*q;j<=i;j*=*q)t[i][*q]+=i/j;for(;~scanf("%d%d",&N,&K);printf("%lld\n",a))for(a=1,q=p;i=*q;q++)a*=1+t[N][i]-t[K][i]-t[N-K][i];} 

 1 #include <stdio.h>
 2 
 3 #define M 431
 4 
 5 int main(void)
 6 {
 7   static int primes[M];
 8   static int sieve[M+1];
 9   static int tbl[M+1][M+1];
10   int *p = primes;
11   int i, j;
12   int N, K;
13 
14   for (i = 2; i <= M; i++) {
15     if (!sieve[i]) {
16       *p++ = i;
17       for (j = i+i; j <= M; j += i) {
18         sieve[j] = 1;
19       }
20     }
21   }
22 
23   for (i = 0; i <= M; i++) {
24     for (j = 0; primes[j] != 0; j++) {
25       int s, t = primes[j];
26       for (s = t; s <= i; s *= t) {
27         tbl[i][t] += i / s;
28       }
29     }
30   }
31 
32   while (scanf("%d %d", &N, &K) != EOF) {
33     long long ans = 1LL;
34     for (i = 0; primes[i] != 0; i++) {
35       const int t = primes[i];
36       ans *= 1LL + tbl[N][t] - tbl[K][t] - tbl[N-K][t];
37     }
38     printf("%lld\n", ans);
39   }
40   return 0;
41 }
poj/2992.c