AtCoder ABC 318 A - Full Moon (灰色, 100 点)

これは意外と難しいと感じた方も多いかもしれない！

• 問題へのリンク

問題概要

正の整数 が与えられる。 日目、 日目、 日目、... には満月が見られる。

日目から 日目までの間で満月が見られる日が何日あるかを求めよ。

解法

前提として、次のことはよく知られている。このことは数学 IA などを学ぶと頻繁に登場する。

---

以上 以下の整数のうち、 の倍数は N / P 個である (N / P は を で割った商)

---

今回の問題もこれに近い。具体的には、満月の日が見られる初日を 日目としてしまおう。つまり、全体的に 日分引くのだ。そうすると、次のように考えられる。

• 日目には満月が見られる
• 日目までに満月は何日分あるか ( 日分引く)

これは、 以上 以下の整数のうち、 の倍数が何個あるかを問う問題だと言える (ただし 日目も数えるので最後に 1 を足す)。

よって、答えは (N - M) / P + 1 である。ただし が より大きい場合は 0 とする。

コード

#include <bits/stdc++.h>
using namespace std;

int main() {
    int N, M, P;
    cin >> N >> M >> P;
    
    if (M > N) cout << 0 << endl;
    else cout << (N - M) / P + 1 << endl;
}