Python3で解く AtCoder Regular Contest 110 A - Redundant Redundancy

問題の制約がゆるすぎて、のときの答えをprintするだけで終わる。

print(2329089562801)

なので、解説記事としては候補のうち最小という状態で考えるとした場合にする。

目次

概要

問題

• 整数が与えられる。
• からまでのすべての整数で割って余りがになるような 以上 以下の値は？

この制約が甘いので、がどんな値でものときの答えを書けば良くなる。

---

解くときに考えた内容

上記のような事があるとしても、考え方としては、でも一緒。

文意から、 からまでのすべての整数で割り切れる数にを足せば、条件を満たす。

ちなみに記事冒頭の値は、30以内の素数を何回かかけた値のうち30以内のものをかけ合わせた値+1である

# 上記のコードでn=30としたときの値を入れてもACにはなる
print(2329089562801)
# ちなみにこれは、30以内の素数を何回かかけた値のうち30以内のものをかけ合わせた値+1である
# 30以内の素数：2, 3, 5, 7, 11, 13, 17, 19, 23, 29
print(2**4 * 3**3 * 5**2 * 7 * 11 * 13 * 17 * 19 * 23 * 29 + 1)
# 2329089562801

---

コード（候補のうち最小とするならば以下）

def gcd(a, b):
    if b == 0:
        return a
    else:
        return gcd(b, a%b)
def lcd(a, b):
    return int(a / gcd(a, b)) * b
def mod_lcd(n, mod):
    ans = 1
    for i in range(2, n+1):
        ans = lcd(ans, i)
    return ans + mod  
n = int(input())
ans = mod_lcd(n, 1)
print(ans)

---

参考になる書籍

• 問題解決力を鍛える!アルゴリズムとデータ構造

けんちょんさんこと、大槻さんの書籍である、「問題解決力を鍛える!アルゴリズムとデータ構造」 ご本人の記事の中で難易度は、螺旋本ということで初学者でも非常に結構読みやすい!!!（実際に、けんちょんさんの記事はC++に疎い自分でも、その思考プロセスを学べるくらい丁寧に書かれているし、この書籍も非常に読みやすい）どのようなステータスの人にもおすすめの一冊になっている。

とうとう発売され自分の手元にも来た（2020-10-03）。現在読み中なのである程度読み込んだら感想を書く予定。めっちゃ図が多いし、章末問題もあるしかなりイケてる。答えはC++で書かれているがそのうちPythonでも書かれるとのことなので、自分で前もってやってしまおうと思う（答え合わせできるのはありがたい）。

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

７章までは別記事に残してある。 blacktanktop.hatenablog.com