超巨大な数を扱う大学入試問題をGoで解いてみる

2015年東京大学（理科）数学 問5

mを2015以下の正の整数とする。${}_{2015} C _m$ が偶数となる最小のmを求めよ
http://kaisoku.kawai-juku.ac.jp/nyushi/honshi/15/t01.html

力技で解く

本当は2015が32*63-1であることを使って2が何回かけられているか調べていくのがエレガントな方法ですが、難しいのでここではまともに計算します。
とはいっても普通に計算するとあっという間にInt64で扱える整数の限界を超えてしまうので、math/big を使います。

tokyo_univ.go

package main

import "fmt"
import "math/big"

var (
    n      = big.NewInt(2015)
    one    = big.NewInt(1)
    two    = big.NewInt(2)
    zero   = big.NewInt(0)
    lookup = make(map[int]*big.Int, 2015)
)

func main() {

    for i := 1; i < 2015/2; i++ {
        x := combination(n, big.NewInt(int64(i)))
        fmt.Println(fmt.Sprintf("%2d : %v", i, x))
        if x.Mod(x, two).Cmp(zero) == 0 {
            fmt.Println("Answer:", i)
            return
        }
    }
}

// 階乗を計算します
func factorial(n *big.Int) (result *big.Int) {

    if n.Cmp(one) < 1 {
        return one
    }

    if m, ok := lookup[int(n.Int64())]; ok {
        return m
    }

    result = new(big.Int).Set(n)
    result = new(big.Int).Mul(result, factorial(n.Sub(n, one)))

    lookup[int(n.Int64())] = result

    return
}

// 組み合わせ n C k を計算します
func combination(n, k *big.Int) *big.Int {

    a := factorial(new(big.Int).Set(k))
    b := factorial(new(big.Int).Sub(n, k))

    c := new(big.Int).Mul(a, b)
    d := factorial(new(big.Int).Set(n))

    return d.Div(d, c)
}

実行結果

$ go run tokyo_univ.go
 1 : 2015
 2 : 2029105
 3 : 1361529455
 4 : 684849315865
 5 : 275446394840903
 6 : 92274542271702505
 7 : 26482793631978618935
 8 : 6647181201626633352685
 9 : 1482321407962739237648755
10 : 297353674437325491072340253
11 : 54199465204257964509094746115
12 : 9051310689111080073018822601205
13 : 1394598100791499491250515513093355
14 : 199427528413184427248823718372349765
15 : 26603632290318802594993084030871458651
16 : 3325454036289850324374135503858932331375
17 : 391034271679024164613170404247882690024625
18 : 43404804156371682272061914871514978592733375
19 : 4562073363172328920910928631495548013141502625
20 : 455294921644598426306910677423255691711521961975
21 : 43253017556236850499156514355209290712594586387625
22 : 3920296227597103631605367710194878440041527511678375
23 : 339702190504392501643021645496451857869685405685869625
24 : 28195281811864577636370796576205504203183888671927178875
25 : 2245472243496894962960570239329006354741564893832280525605
26 : 171864990944570037549674414471720101766758236104855317152075
27 : 12660720999583326099492681866083380830151190059724341696869525
28 : 898911190970416153063980412491920038940734494240428260477736275
29 : 61590915050283341246142382055911900599146187588128653571353861325
30 : 4077318576328757190494625692101367819663477618334116866423625619715
31 : 261079915290728484617155870929716616839742034593329741285512801778525
32 : 16186954748025166046263663997642430244064006144786443959701793710268550
Answer: 32

というわけで、答えは32です。71桁ありますね。
math/big、ちょっと使いづらいところもありますがこのような超巨大な数を扱うことができます。