👻

ABC 052 C - Factors of Factorial のメモ

2023/05/25に公開

AtCoder

競プロ

tech

解いてみました。

考察

階乗ですね。最大だと1000の階乗で、とてつもない数になるので実際に求めるわけにもいきません。
しかし、 $N$ が小さければ特に問題なく求められるので、 $N$ が小さい場合の答えをいくつか愚直に求めて検証してみました。主に $(N - 1)!$ の場合の答えと $N!$ の場合の答えの差分に注目しました。

それでわかったのは、 $N$ が素数の場合は $N!$ の場合の答えは $(N - 1)!$ の場合の答えの2倍になることでした。おそらく、 $(N - 1)!$ を因数分解した数それぞれに対して $N$ を掛けた数が新たな約数になるからなのだろうと。
$N$ が素数でない場合は、2倍よりは小さい値となっていました。素数でない場合は、因数と $N$ を掛けた数と同じ数が既に $(N - 1)!$ の因数の中に存在する可能性があるので、重複が排除される分減るのかなと思いました。
なので、素数の場合は答えを倍にして、素数でない場合は倍にした後に重複する数の個数分引くという操作で求められるのかなと考えました。
しかし、重複する数の個数を定数時間で求められる方法を見つけられず。一応もう少し進んで、 $N$ が素数でない場合は $N$ 自身だけでなく、 $N$ を因数分解した各数値も考慮しないといけないことには気づいたりもしたのですが、そもそもこの考え方だと因数を全部保持しないといけなくて、それは全然無理なのでこの観点から解くのはあきらめました。

そもそも約数の個数の求め方なんて普通に定石があるのではとようやく思い至って調べました。ググるとやはり普通に見つかって、 $N$ を素因数分解した時の各素因数の次数に1を足した数を全てかけ合わせればよいということでした。

たとえば360を素因数分解すると $2^3 \times 3^2 \times 5^1$ となります。これで上記の計算を行うと $(3 + 1) \times (2 + 1) \times (1 + 1)$ で、24個とわかります。

これで求められそうです。 $N!$ 自体はエグイ数になるけど、 $N!$ を素因数分解した結果を保持するのなら問題なさそうで。
ただ、階乗を求めてから素因数分解はもちろん無理です。しかし1から $N$ までの各数値に対してまず素因数分解をして次数を求めて、それをマージするという操作なら現実的な時間で処理できそうです。

実装

fun main() {
    val n = readLine()!!.toInt()
    val primeFactorials = (1..n).map { primeFactorial(it.toLong()) }

    val map = mutableMapOf<Long, Long>()

    val mod = 1000000007

    for(pfs in primeFactorials) {
        for(pf in pfs) {
            map[pf.first] = map.getOrDefault(pf.first, 0) + pf.second
        }
    }

    var ans = 1L
    for((_, value) in map) {
        ans = (ans % mod) * ((value + 1) % mod) % mod
    }

    println(ans % mod)
}

fun primeFactorial(paramN: Long): List<Pair<Long, Long>> {
    val result = mutableListOf<Pair<Long, Long>>()
    var n = paramN
    var a = 2L
    while(a * a <= n) {
        if(n % a != 0L) {
            a++
            continue
        }
        var ex = 0L

        while (n % a == 0L) {
            ex++
            n /= a
        }
        result.add(a to ex)
        a++
    }
    if(n != 1L) {
        result.add(n to 1)
    }
    return result
}

素因数分解は以前使ったものを流用しました。
内容として上で書いた通りですが、オーバーフローしないように随時modをとる必要があります。

（執筆時間: 27分2秒）

考察

実装

Discussion