yu/logs/*

技術メモ など

AtCoder ABC048 B 解法メモ a以上b以下の整数のうち、xで割り切れるものの個数を求めたい

ちょっと躓いたのでメモ

解いていた問題

atcoder.jp

解法メモ

  • ポイントは3つ

    1. 大前提:「a(a>0)以下の整数のうちxで割り切れるものの個数」 = 「a/x ※小数点以下切り捨て」

      • ex) 8以下の整数のうち2で割り切れるものの個数は8/2=4個(2, 4, 6, 8の4個)
      • (ここを失念していてハマりました・・・)
    2. a以上b以下の範囲を求めたい場合は、「b以下の範囲」 - 「a-1以下の範囲」で求められる

      • ex) 4以上8以下の整数のうち2で割り切れるものの個数は・・・(入力例1のケース)
        • 8以下の整数のうち2で割り切れるものの個数:4個(2, 4, 6, 8の4個) ・・・ ①
        • 3以下の整数のうち2で割り切れるものの個数:1個(2の1個) ・・・ ②
        • ① - ② で3個(4,6,8の3個)
    3. 0はx(x>0)で割り切れる*1

  • 1、2をベースにしつつ、3の0が含まれるケースを処理してあげると解くことが出来た

提出した回答

*1:よく考えたらそれはそう