問題概要

$a$ 以上 $b$ 以下の整数のうち、 $x$ の倍数は何個あるか？

制約

$0 \le a \le b \le 10^{18}$
$1 \le x \le 10^{18}$

考えたこと

制約が $10^{18}$ と極めて大きいので探索手法で解くことは難しい。数学的に求めることを考える。

まず、「 $a$ 以上 $b$ 以下の整数のうち、条件を満たすものの個数」を問う問題では、次のように言い換えることがしばしば有効である。

( $1$ 以上 $b$ 以下の整数のうち、条件を満たすものの個数)
- ( $1$ 以上 $a-1$ 以下の整数のうち、条件を満たすものの個数)

但し、今回は $a = 0$ という場合がありうるので注意しよう。そのような場合はあとで考えることにして、 $a \ge 1$ として考えよう。

一般に、次のことが言える。

$1$ 以上 $K$ 以下の整数のうち、 $x$ の倍数の個数は K / x ( $K$ を $x$ で割ったときの商) と表せる

よって、求める答えは次のようになる ( $a = 1$ でも正しい)。

b / x - (a - 1) / x 個

$a = 0$ の場合

残るは $a = 0$ の場合だ。 $0$ も $x$ の倍数であることに注意すると、この場合は、

( $1$ 以上 $b$ 以下の $x$ の倍数の個数) + 1

が答えとなる。よって、

b / x + 1 個

と表せる。

コード

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

int main() {
    long long a, b, x;
    cin >> a >> b >> x;
    
    // 1 以上 b 以下の x で割り切れる個数
    long long upper = b / x;
    
    
    if (a == 0) {
        // 0 も x で割り切れるので 1 を足す
        cout << upper + 1 << endl;
    } else {
        // (a-1) 未満の x で割り切れる個数を求めて引く
        long long lower = (a - 1) / x;
        cout << upper - lower << endl;
    }
}