WARush

SRMの結果とか、解けた問題のコードを書いていきます

SRM569 Div2 Hard "MegaFactorialDiv2"

問題

http://community.topcoder.com/stat?c=problem_statement&pm=12400

n!kを次のように定義する

  • n!k = n!(k-1) * (n-1)!k ( n > 0 and k > 0 )
  • n!k = 1 (n = 0)
  • n!k = n (k = 0)

例えば、7!1は7!(普通の階乗)となり、5!3 = 5!2 * 4!3 = (5!1 * 4!2) * 4!3となる。

N, Kが与えられるので、N!Kの約数の数を返せ。

制約

1 <= N <= 1000
1 <= K <= 100


考えた事

例えば12だったら1, 2, 3, 4, 6, 12
25だったら1, 5, 25
30だったら1, 2, 3, 5, 6, 10, 15, 30

約数を数え上げるにはN!Kを素数の何乗かに変形すればよさそうだな~。
N!K = 2^a + 3^b + 5^c + 7^d + ...

まず4!とか7!とかF!が何回かけられるのかを出そう。

例えば4!1だと
4! 3! 2! 1!
1  0  0  0

4!2だと
4! 3! 2! 1!
1  1  1  1

4!3だと
4! 3! 2! 1!
1  2  3  4

4!3だと
4! 3! 2! 1!
1  3  6  10

何かDPの表っぽい?

N=4の時の表

4! 3! 2! 1!
K=1 1 0 0 0
K=2 1 1 1 1
K=3 1 2 3 4
K=4 1 3 6 10

dp[F!][K] = dp[F+1!][K] + dp[F][K-1]で更新できそう。

これでF!が何回かけられるかが分かった。

ここから整数Aが何回かけられるかを求めよう。
例えば4!3だと

4! 3! 2! 1!
1  2  3  4

だが、これは

 4 * 3 * 2 * 1
     3 * 2 * 1
     3 * 2 * 1
         2 * 1
         2 * 1
         2 * 1
             1
             1
             1
             1
 -------------
 1   3   6  10

こうゆうことだから、大きい方(4!)から順に
足していって、累積したものを見ていけば大丈夫そうだな。

ここから素数が何乗かに直そう。
素数を2, 3, 5, 7, 11...と順に見ていく。
素数2を見ていく時は、
まず2で割り切れる2,4,6,8...のかけられた数を足していく。
4の倍数のものは2^2だから、かけた数を2回足さないといけないので、
さらに4で割り切れる4,8,12,16....のかけられた数を足していく
8の倍数のものは2^3だから、かけた数を3回足さないといけないので、
さらに8で割り切れる8,16,24,32....のかけられた数を足していく
16のb(以下略

 2 4 6 8 10 12 14 16
   4   8    12    16
       8          16
                  16
 -------------------
 1 2 1 3  1  2  1  4 ←足される回数

全てを足したものが2の乗数となる。
これを1000までの素数全てでやっていく。


あとはSRM569 Editorials に書いてある通り、各素数の乗数+1をかけていけばやっと答え。

例)
60 = 2^2 * 3^1 * 5^1

2^0 * 3^0 * 5^0 = 1
2^0 * 3^0 * 5^1 = 5
2^0 * 3^1 * 5^0 = 3
2^0 * 3^1 * 5^1 = 15
2^1 * 3^0 * 5^0 = 2
2^1 * 3^0 * 5^1 = 10
2^1 * 3^1 * 5^0 = 6
2^1 * 3^1 * 5^1 = 30
2^2 * 3^0 * 5^0 = 4
2^2 * 3^0 * 5^1 = 20
2^2 * 3^1 * 5^0 = 12
2^2 * 3^1 * 5^1 = 60

(2+1) * (1+1) * (1+1) = 12通り

ソースコード

const int MOD = 1000000009;

class MegaFactorialDiv2 {
public:

    int countDivisors(int N, int K){
        // F!が何回かけられたかを取得
        int F[1010];
        memset( F, 0, sizeof(F) );
        F[N] = 1;
        for( int k = 2; k <= K; k++ ){
            for( int f = N; f >= 2; f-- ){
                F[f] = (F[f] + F[f+1]) % MOD;
            }
        }

        // 整数Aが何回かけられたかを取得
        int A[1010];
        memset( A, 0, sizeof(A) );
        for( int i = N; i >= 2; i-- ){
            A[i] = (A[i+1] + F[i]) % MOD;
        }

        // 素数Pが何回かけられたかを取得
        bool isPrime[1010];
        memset( isPrime, true, sizeof(isPrime) );
        int P[1010];
        memset( P, 0, sizeof(P) );
        // 全ての素数を見ていく
        for( int p = 2; p <= 1000; p++ ){
            if( !isPrime[p] ) continue;
            // 素数の倍数を見ていく
            for( int d = p; d <= 1000; d *= p ){
                for( int n = d; n <= 1000; n += d ){
                    P[p] = (P[p] + A[n]) % MOD;
                    isPrime[n] = false;
                }
            }
        }

        // 素数の乗数から結果を計算
        long long res = 1;
        for( int i = 0; i <= 1000; i++ ){
            res = res * (P[i] + 1) % MOD;
        }
        return (int)res;
    }
};