学習記録：Java：A31 - Divisors , 競技プログラミングの鉄則 演習問題集

はじめに

競技プログラミングの鉄則　演習問題集　の　A31 - Divisors を解いたので、その備忘録を！

ポイントとミスったポイント

ポイント

• 包除原理を使う。高校数学で学ぶ集合的なイメージ。重なり合っている部分は重複して数えちゃうから引こうね！ってこと！
• 3の倍数が何個あるか？という問題だから、普通に3で割った数が3の倍数の個数だよね。
• 5の倍数も3の倍数と一緒。

ミスったポイント

• 数え上げちゃった。計算量がバカでかい。O(3N)
  • 正解は4回計算するだけで行けちゃう。
• long使っていない。intじゃ、小さすぎて正しく表示できないよ。

目次

問題と公式の解答

A31 - Divisors https://atcoder.jp/contests/tessoku-book/tasks/tessoku_book_ae

公式の解答へのリンク https://github.com/E869120/kyopro-tessoku/blob/main/codes/java/chap05/answer_A31.java

解答例

import java.util.Scanner;

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

        // 数える用の変数を用意するよー
        // 正直用意しなくてもいいよ。公式見てみて。すっきりしている。
        long threeCnt = 0, fiveCnt = 0, fifteenCnt = 0;

        threeCnt = n / 3;
        fiveCnt = n / 5;
        fifteenCnt = n / (5 * 3);


        System.out.println(threeCnt + fiveCnt - fifteenCnt);
        sc.close();
    }
}

誤った回答例（TLE）

時間超過しちゃうよー。計算量がバカでかいからねー。

import java.util.Scanner;

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

        // 数える用の変数を用意するよー
        int threeCnt = 0, fiveCnt = 0, fifteenCnt = 0;

        for (int i = 1; i <= n; i++) {
            if (i % 3 == 0) {
                threeCnt ++;
            }

            if (i % 5 == 0) {
                fiveCnt ++;
            }

            if (i % (3 * 5) == 0) {
                fifteenCnt ++;
            }
        }

        System.out.println(threeCnt + fiveCnt - fifteenCnt);
        sc.close();
    }
}