桃の天然水

■[Scala]ScalaでProject Euler（144）

Problem 97

これはシェルピンスキー数というものを調べているときに発見された巨大素数らしいです。

多倍長整数を使えば、

println (((BigInt(1) << 7830457) * 28433 + 1) % 1e10.toLong)

これだけです。

しかし、いくらなんでもこれでは芸が無いので、64ビットの範囲で解きます。10桁で計算し、掛け算するときは5桁ごとに分けて計算します。簡単ですね。

val D = 1e10.toLong
val M = 1e5.toLong

def mul(x :Long, y :Long) :Long = {
    val (x1, x2) = (x / M, x % M)
    val (y1, y2) = (y / M, y % M)
    ((x1 * y2 + x2 * y1) * M + x2 * y2) % D
}

def pow(n :Int, e :Int) :Long =
    if(e == 0)
        1L
    else {
        val m = pow(n, e / 2)
        if(e % 2 == 1)
            mul(mul(m, m), n)
        else
            mul(m, m)
    }

println ((mul(pow(2, 7830457), 28433) + 1) % D)