ARC091-D:Remainder Reminder(400)

数え上げ 2変数

問題

https://beta.atcoder.jp/contests/arc091/tasks/arc091_b

1 <= a, b <= n である a, b が与えられる。a % b >= k である個数を求めよ。

制約

  • 1 <= n <= 105
  • 1 <= k <= n-1
    入力値は整数

考え方

a_n = {1, 2, 3, ..., n}, b_n = {1, 2, 3, ..., n} の2つの数列が与えられていると考えて良い。2つの要素が与えられて、ナイーブ解がO(N2)になるときの計算量を落とす時の典型は「片方を固定してもう片方については同じ要素/性質をまとめて数え上げる」である。ABC-Dでは非常によく出てくるテクニックである。

さて、今 b_i を固定するとしよう。どのように状態をまとめられるか考えてみる。

k = 0 の場合は明らかに n2 個存在する。以下では k >= 1 とする。

参考に N = 5 の場合について、a_i を b で割った余りを以下に記載する。

b 1 2 3 4 5
1 0 0 0 0 0
2 1 0 1 0 1
3 1 2 0 1 2
4 1 2 3 0 1
5 1 2 3 4 0

(1)上記の表のように a_i を b で割ったときの余りは 1,.., b-1, 0 が繰り返される。繰り返される 1,.., b-1, 0 のまとまりは全部で floor(N/b) 回あらわれる。その中に k 以上の数は (b-k) 個ある。ただし b-k < 0 となる場合は 0 個とする。

(2)また、 1,.., b-1, 0 が floor(N/b) 回繰り返されたあとに残っている数は N % b 個ある。この中に k 以上の数が N % b - k + 1 個ある。ただし N % b - k + 1 < 0 となる場合は 0 個とする。

よって、ある b について求める個数は floor(N/b) * (b-k) + N%b-k+1 となる。これは O(1) で求められるので全体の計算量は O(N) となり間に合う。

       public void solve(int testNumber, InputReader in, PrintWriter out) {

            long n = in.nextLong(), k = in.nextLong();
            long sum = 0;

            for (int b = 1; b <= n; b++) {
                sum += max(0, b-k)*(n/b) + max(0, n%b-k+1);
            }
            if (k == 0) sum = n*n;
            out.println(sum);
        }

ポイント

  • 2変数の場合は、片側固定で片方の状態をまとめて数え上げる。
  • あまりは循環する