Go言語のmath/bigを使って競プロ

Atcoder ARC 057 C 二乗根

コンテスト中には解けなかったけど、Goで多倍長整数を扱ったことがなかったので。

問題

http://arc057.contest.atcoder.jp/tasks/arc057_c

解説

http://arc056.contest.atcoder.jp/data/arc/057/editorial.pdf

mayokoex.hatenablog.com

L = input()
R = (L+1)*(L+1)-1
L = L*L
while (L+99)/100 <= R/100:
    L = (L+99)/100
    R = R/100

print L

PythonのこれをGoでやります

Go言語で多倍長

有効桁数が1≦k≦1000なので多倍長整数を使います。

競技プログラミング多倍長整数を使うときは、だいたい以下

  • C++で自作の多倍長ライブラリを使う

  • C++でboostライブラリを使う(AtCoderなら使える!!)

  • Python等をつかう

Goだとmath/bigライブラリですが、このままだと使いづらいので以下を参考に関数を用意した。

stackoverflow.com

提出コード

Submission #801740 - AtCoder Regular Contest 057 | AtCoder

package main

import (
    "fmt"
    "math/big"
)

func main() {
    var s string
    fmt.Scan(&s)
    a := new(big.Int)
    a.SetString(s, 10)  // 文字列を10進数としてbig.Intに変換
    r := Sub(Mul(Add(a, big.NewInt(1)), Add(a, big.NewInt(1))), big.NewInt(1))
    l := Mul(a, a)

    for Div(Add(l, big.NewInt(99)), big.NewInt(100)).Cmp(Div(r, big.NewInt(100))) != 1 {
        l = Div(Add(l, big.NewInt(99)), big.NewInt(100))
        r = Div(r, big.NewInt(100))
    }

    fmt.Println(l)
}

func Add(x, y *big.Int) *big.Int {
    return big.NewInt(0).Add(x, y)
}

func Sub(x, y *big.Int) *big.Int {
    return big.NewInt(0).Sub(x, y)
}

func Mul(x, y *big.Int) *big.Int {
    return big.NewInt(0).Mul(x, y)
}

func Div(x, y *big.Int) *big.Int {
    return big.NewInt(0).Div(x, y)
}

演算子オーバーロードがほしい