集合の要素の個数

もうほぼアルゴリスムでもなんでもなく、数学の知識のメモみたいになってますが、、、（笑）

下記問題を復習していたら、全く解き方がわからず、習得していなかったので必死にググって理解しました。

atcoder.jp

参考

下記がほぼ同じ問題を数学として（？）解説してくれています。

math.nakaken88.com

考察

上記では1~100までの数字のうち、2で割り切れる個数はいくつか？みたいな問題です。
これの場合は単純に100 / 2でOK。
さらに発展問題として101 ~ 300 までの数字で3で割り切れる個数はいくつか？という問題の解説もあります。
解説を見てみると、 100 / 3 は33.33333... なので100までで3で割り切れる個数は33個。
300までなら300 / 3 = 100個。なので100 - 33 = 67 という解説になっていました。

AtCoderの問題は、A ~ Bまでの数字でxで割り切れる個数は？という話です。

例1をみてみる

4 ~ 8 の数字の中で 2 で割り切れる個数はいくつか？
という問題になります。もちろん入力値が10¹⁸とかで無ければ１個ずつループさせるだけの楽勝問題なのでこんな知識も必要ありません。

まず、参考URLの通り、8 / 2 をします。そうすると　もちろん答えは4です。
Aである4までで2で割り切れる個数は2ですが、B部分と一個重複します。重複している数字は4です。
そのため、8 / 4 - (4-1) / 2という数式が出現するわけですね！

例2をみてみる

0 ~ 5 の数字の中で1で割り切れる個数はいくつか？
5 / 1 で 5ですね。でも 0 / 1 = 0なので割り切れる判定としてOKなので、5 + 1 = 6が答えになります。
なのでAが0だった場合、 5 / 1 + 1としなければいけません。

例3をみてみる

9 ~ 9 の間で 2で割り切れる個数
9 / 2 - (9-1) / 2 = 0 （厳密にいうと0.5になりますが、これはint/longの変数にぶちこむことで0となります）

例4をみてみる

1 1000000000000000000 3
1000000000000000000 / 3 - (1 - 1) / 3 = 333333333333333333

これで、理解できたかな。
僕のように、文系出身でサクッと理解が難しい人の助けになれれば幸いすぎます。

サンプルコード

import java.util.Scanner;

public class Main110 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long a = sc.nextLong();
        long b = sc.nextLong();
        long x = sc.nextLong();
        sc.close();

        long ans = 0;
        if(a == 0) {
            ans = b / x + 1;
        } else {
            ans = b / x - (a - 1) / x;
        }
        System.out.println(ans);
    }
}