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; } };