くろたんく雑記帳

日常とか、わんちゃんとか、機械学習とか、競プロとか、

MENU
トップ > AtCoder > Python3で解く AtCoder Beginner Contest 179 C - A x B + C

Python3で解く AtCoder Beginner Contest 179 C - A x B + C

AtCoder 競プロ ABC-C 約数の個数

ある数の約数を数える場合は素因数分解を使えばいいが、今回は制約が大きいので、素因数分解して、全てのパターンを計算すると間に合わない。{\displaystyle N=i}から{\displaystyle N=N}までの約数の個数をカウントするなら定数倍的に考える方がいい。

目次

概要

問題

  • 正整数{\displaystyle n}が与えられる。
  • {\displaystyle a \times b + c = n}を満たす正整数の組{\displaystyle (a, b, c)}はいくつある？

解くときに考えた内容

  • 約数の個数のカウントだからと言って素因数分解の素数が何回かけられているかっていう風に考えると計算量でダメ。
  • 全パターンのをカウントするので定数倍的に考える。
  • {\displaystyle a \times b}だけに着目すればいい。
  • なぜなら、{\displaystyle c}と{\displaystyle a \times b}は1対1対応するので、
    • 例えば{\displaystyle n=4}の時
    • {\displaystyle c=1}, {\displaystyle a \times b = 3}
    • {\displaystyle c=2}, {\displaystyle a \times b = 2}
    • {\displaystyle c=3}, {\displaystyle a \times b = 1}
  • ここで、
    • {\displaystyle a = 1}の時{\displaystyle a \times b \leq n-1}となるような{\displaystyle b}はいくつあるか
    • {\displaystyle a = 2}の時{\displaystyle a \times b \leq n-1}となるような{\displaystyle b}はいくつあるか
    • のように{\displaystyle a = n-1}の時までを考えると、その値は{\displaystyle \frac{n-1}{a}}の整数部分である。 図を示すと以下のようになる
      f:id:black_tank_top:20200920002252j:plain
      約数の数のカウントを定数倍で考えた時と、素因数分解で考えた時の図

{\displaystyle a}の1-12の列のマス目の値は{\displaystyle b}の値。

{\displaystyle n = 13}とすると、{\displaystyle a \times b \leq 12}になる場合を考えると、{\displaystyle a = 1}の時、{\displaystyle b}は{\displaystyle 12}個取りうる。{\displaystyle a = 2}の時、{\displaystyle b}は{\displaystyle 6}個取りうる。といったように、図で言うと、縦方向に約数の候補を見ていくイメージにで考える。そうすると、計算量は{\displaystyle O(n)}でおさまる。

ちなみにこの図で言うと、横方向に見ると、素因数分解で約数を数えて、組み合わせ数を出しているイメージになる。

コード

n = int(input())
cnt = 0
# aが1からn-1まで動くと考える
for a in range(1, n):
    # a*bがn-1以下であると考える
    cnt += (n-1) // a
print(cnt)

書籍

アルゴリズムの参考書籍
  • 問題解決力を鍛える!アルゴリズムとデータ構造
    けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも結構読みやすいのではないかと期待。（というのもけんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているので）
    投稿時点では、まだ発売前だけど、すでにベストセラー。予約しておかないとすぐ手元に来ないかも!?と思って速攻ポチった。

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

問題解決力を鍛える!アルゴリズムとデータ構造 (KS情報科学専門書)

  • 作者:大槻 兼資
  • 発売日: 2020/10/02
  • メディア: 単行本（ソフトカバー）

drken1215.hatenablog.com

いわゆる、螺旋本。Aizu Online Judgeの問題を題材に解説されている。自分としては、 Aizu Online Judgeは最近はβ版運用中で、構成がアルゴリズムの項目ごとに問題がタグ付けされているようなイメージで、ここら辺弱いから集中的にやってみようっていう感じでできるので、いいと思っている。（AtCoderもそんな感じのリスト作って欲しい） ただ、この書籍はC++で書かれているのでPythonでやる場合はあくまでもその過程の考え方を参考にし自分で実装する必要がある。（AOJも解いているので、記事にしていこうかなぁ）

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造

プログラミングコンテスト攻略のためのアルゴリズムとデータ構造