AtCoder ABC 131 C - Anti-Division (Go) - あるエンジニアのAtCoder奮闘記

irisruneです。久々にコンテストに参加した結果、5完で1242→1292とレートが伸びました。

問題

典型テクニックの寄せ集めのような問題だと思います。

なお、コンテスト本番でPythonを使う度胸はなかったので久々にGo言語で書いております。

package main

import (
    "bufio"
    "fmt"
    "os"
    "strconv"
)

var sc *bufio.Scanner

func nextInt() int {
    sc.Scan()
    i, e := strconv.Atoi(sc.Text())
    if e != nil {
        panic(e)
    }
    return i
}

func gcd(x, r int) int {
    if x < r {
        x, r = r, x
    }
    if x%r == 0 {
        return r
    }
    return gcd(r, x%r)
}

func main() {
    sc = bufio.NewScanner(os.Stdin)
    sc.Split(bufio.ScanWords)
    a, b, c, d := nextInt(), nextInt(), nextInt(), nextInt()
    a--
    cd := (c * d) / gcd(c, d)
    fmt.Println((b - ((b / c) + (b / d) - (b / cd))) - (a - ((a / c) + (a / d) - (a / cd))))
}

この問題のポイントは2つあります。1つ目のポイントは $C,D$ どちらでも割り切れない値の個数の求め方です。これは高校数学で習う、場合の数の性質を使うと、

$C,D$ どちらでも割り切れない値の個数 $=$ 全体の値の個数 $-C,D$ どちらかで割り切れる値の個数
$C,D$ どちらかで割り切れる値の個数 $=$ $C$ で割り切れる値の個数 $+D$ で割り切れる値の個数 $-C,D$ どちらでも割り切れる値の個数

となることが示せます。また、

$C,D$ どちらでも割り切れる値の個数 $=$ $C,D$ の最小公倍数で割り切れる値の個数
$C,D$ の最小公倍数 $=$ $(C\times D) / C,D$ の最大公約数

という性質があります。これらの性質を使うことで $X$ 以下の整数のうち $C,D$ どちらでも割り切れない値の個数を求めることができます。

2つ目のポイントは $[A,B$ ]に対しての $C,D$ どちらでも割り切れない値の個数の求め方です。これを求める方法は2通りあり、

$[A,B$ ]の各値に対し繰り返し処理などで $C,D$ どちらでも割り切れないことを判定する。
$B$ 以下の整数のうち $C,D$ どちらでも割り切れない値の個数と $A$ 未満の整数のうち $C,D$ どちらでも割り切れない値の個数との差を求める。

計算量について考えると前者は $O(B)$ 、後者は $O(1)$ となりますが、 $A,B\leq10^{18}$ という条件から使えるアルゴリズムは後者のみとなります。

後者のアルゴリズムですが、前もって導き出した $X$ 以下の整数のうち $C,D$ どちらでも割り切れない値の個数を求める方法を $A-1,B$ に対して適用することで答えを求めることができます。

コードを見直してみると、最大公約数を求める部分は関数化していますが、 $X$ 以下の整数のうち $C,D$ どちらでも割り切れない値の個数を求める関数も実装しておいた方がよりわかりやすかったと思います。

雑記

実は最大公約数を求める関数はGoの標準パッケージにもあるのですが…どういうわけか多倍長変数パッケージに実装されているので、自作ライブラリを使った方が使いやすいような気がします。
- Pythonを触った後なのでなおさら実感するのですが、max,min関数がInt型になかったりなど痒いところに手が届かないことが多いのが難点です。毎回自作ライブラリを貼ってもいいのですがコード長がえらいことになりがちですね。