はじめに
カテゴリー競プロ初中級者100問では、Qiitaにて@e869120さんがレッドコーダーが教える、競プロ・AtCoder上達のガイドライン【中級編：目指せ水色コーダー！】としてまとめられている100問をPythonで解いています。
全問題の一覧はこちらです
問題
https://atcoder.jp/contests/abc139/tasks/abc139_d
この問題は簡単な数学的考察で解くことができます。
方針
まず答えの上限について考えます。ある数をnで割った時の余りは最大でn-1であるため、解は最大で0 + 1 + 2 +..+ N-1となることが分かります。
実は任意のNについてそのような解を、以下のようなパターンで実現できます。Nmod1 + 1mod2 + 2mod3 + (N-1)modN
結局、解は0 + 1 + 2 +..+ N-1を求めれば良いということになります。これはシグマ公式によりO(1)で求めることができます。
コード
1 | N = int(input()) |
記事情報
- 投稿日：2020年5月22日
- 最終更新日：2020年5月22日