今週もプログラミングコンテストに参加したので考察を書いていきます。今週は ABC-only です。

## AtCoder Beginner Contest 114

問題一覧：

## A - 753

問題概要：いまX歳の高橋くんが、七五三で祝われるか判定せよ。

考察：X が 7 か 5 か 3 であれば YES です。

筆者の回答 [AC]

## B - 754

問題概要：N の連続する3桁を取り出した整数を X とするとき、 |X - 753| の最小値を求めよ。

考察：例えば 31415 なら X = 314, 141, 415 のうち、どれがもっとも 753 と近くて、そのときの差はいくらか？ という話です。

すべての X を実際に計算すればOKです。

筆者の回答 [AC]

## C - 755

問題概要：1以上N以下の整数のうち、どの桁の数字も 7,5,3 のいずれかで、しかも 7,5,3 がどれも1回以上現れる、というものを数えよ。

考察：これとほぼ同様の問題を前にやりました。 (#11 「全列挙」)

一見、桁DPをやるようにみえますが、条件を満たす数が少ないので全列挙で解けます。「どの桁の数字も 7,5,3 のいずれか」であるような9桁の数は 3^9 = 19683 個。

筆者の回答 [AC]

## D - 756

問題概要：N! の約数のうち、約数がちょうど75個である数を数えよ。

考察：結論からいうと、約数の公式と素因数分解を使いつつ、泥臭く数え上げることで解けます。

はじめ、N=100 のケースで答えが 543 個なので、C問題と同じく「約数が75個である数」を全列挙すればOK？ と思いましたが、100! を実際に計算するのが厳しいので保留しました。

100! は約360桁の数なので、 u64 (64ビット整数) で表せません。(多倍長整数でどうかは考えてませんでした)

## 約数の条件

約数が75個である条件を変形してうまく数える、という方針を検討します。約数の個数は、素因数分解を行うと簡単に計算できるという公式があります:

約数の個数の公式と平方数の性質 | 高校数学の美しい物語

例えば 10! = 2^8・3^4・5^2・7^1 なので約数の個数は (8+1)・(4+1)・(2+1)・(1+1) = 270 です。

仮に n の約数が75個あるとします。約数の個数の公式から、n を素因数分解したときの積の形は絞られます。例えば n = p^2・q^4・r^4 とか n = p^2・q^14 とかです。(75 = 3・5^2)

ここで **重複度** という語を定義しておきます。素因数分解の右肩に出てくる数を重複度と呼ぶことにします。例えば 10! = 2^8 ・3^4・5^2・7^1 なので、 10! における素数 2 の重複度は 8 です。これは 10! は 2 で8回割れることと同じです。

**約数の関係は重複度を使うと単純に言い表せます** 。d が M の約数であるとき、 d を p で m 回割れるなら M も m 回割れます。つまり、

    d が M の約数
    ⇔ d が M を割り切る
    ⇔ (dにおけるpの重複度) ≤ (Mにおけるpの重複度) (p: 素数)

がいえます。

例えば 2^4・3^4・5^2 は 10! (= 2^8・3^4・5^2・7^1) の約数です。(象徴的に書けば (4, 4, 2, 0) ≤ (8, 4, 2, 1))

以上から次の計算手順が導けます。

1. N! を素因数分解する。
2. 約数が75になる素因数分解の各パターンにつき、 N! の約数を数える。

## 素因数分解の計算

指数法則 a^x・a^y = a^(x+y) から、《積の素因数分解は素因数分解の「和」》といえます。例えば 6・10 の素因数分解は 2^2・3・5 ですが、これは 6=2・3 と 10=2・5 の重複度を足し合わせたものになっています。

そのため N! の素因数分解をするには 1~N をそれぞれ素因数分解して足せばいいです。

素因数分解のアルゴリズムはいろいろ研究されているっぽいですが、今回は単にループして割るだけでOK。

まず n を 2 で可能なかぎり割ることで、2 の重複度が分かります。次に 3 でも同じことをします。

次に 4 では割れないというのがポイントで、カウンター変数 i が素数かどうかは気にしなくてかまいません。(いま n は i 未満の数で割れないようにしたので、i で割れるなら i は素数といえる。)

## 数え上げ

こうして各素数の重複度は分かりました。あとは数え上げです。ここは数学定理とか使わなくて、地道にがんばります。

n = p^2・q^4・r^4 の形をした約数75の数を数えるには、重複度 2 以下の素数を1個と、別の重複度4以上の素数2個を選ぶ組み合わせを計算すればいいです。

重複度が2以下の素数が x 個、重複度が4以上の素数が y 個あるとします。まず重複度が2以下の素数を使うケースを数えると、 x・C(y, 2) です。重複度が2以下の素数を使わないケースを考えると、 3・C(y, 3) です。

ほかのケース (2,24; 4,14; 74) についても同様に計算したら、ひと仕事おしまい。

筆者の回答 [AC]

めんどくさい問題ですが、こういうのをしっかりやっていく腕力が大事です。

おわりに

全完できました。数学ガールがいま熱いので読みましょう。

コメントやマシュマロでご意見ご感想ください！