【競プロ精進ログ】ABC131-C

zuka

ABCをコツコツ解いていきます。

本記事は，管理人の競技プロ精進日記としてログを取ったものです。モチベーションを爆上げするために，積極的にアウトプットしていく作戦です。これから競技プログラミングを始めようと考えている人や，なんとなく敷居が高いと感じている人の参考になれば嬉しく思います。その他の記事は以下をご覧ください。

本記事の概要

Atcoderで初心者用のコンテストとして開催されているAtcoder Beginner Contest（通称ABC）を解いていくものです。今回はABC131-C「Anti-Division」です。

ポイント

今回の問題でおさえるべきは「中途半端な区間の処理」です。$A$以上$B$以下の区間における$C$の倍数を$f(A:B)$と書くことにします。このとき，$f(A:B)$は$0$以上$B$以下の$C$の倍数$f(0:B)$から，$0$以上$A-1$以下の$C$の倍数$f(0:A-1)$を引けば求められます。

これを$D$の倍数についても行えばOKです。ただし，問題で出力しなくてはならないのは「$C$でも$D$でも割り切れない数」です。これは，「$C$の倍数と$D$の倍数の和集合の補集合」になります。これは包含と排除の原理を利用すればOKですね。和集合の基本的な求め方です。

具体的には，「$C$の倍数と$D$の倍数の和集合」は「$C$の倍数＋$D$の倍数ー$CD$の最大公約数の倍数（共通部分）」です。注意しなくてはならないのが，最大公約数が絡んでくる点です。最大公約数の代わりに$CD$を考えてしまうと，$C$の倍数と$D$の倍数の共通部分ではなくなってしまいます。

最大公約数は，基本的にユークリッドの互除法を用いて計算していくことになります。詳しくは，以下の記事をご覧ください。

あわせて読みたい

【c++で楽しく実装！】ユークリッドの互除法 本記事では，ユークリッドの互除法の簡単な解説と実装例をお伝えしていきます。使用言語はc++です。その他の競技プログラミング関連の記事は，以下の目次をご覧ください...

実装

#include <bits/stdc++.h>
#define _GLIBCXX_DEBUG
#define rep(i, n) for (int i = 0; i < (int)(n); i++)
#define repi(i, a, b) for (int i = (int)(a); i < (int)(b); i++)
using namespace std;
typedef long long ll;

// 最大公約数をユークリッドの互除法で求める
ll gcd(ll a, ll b) {
  return b!=0 ? gcd(b, a % b) : a;
}

ll a, b, c, d, cnt_c, cnt_d, cnt_cd;

int main(){
  cin >> a >> b >> c >> d;
  // cの倍数
  cnt_c = b/c - (a-1)/c;
  // dの倍数
  cnt_d = b/d - (a-1)/d;
  // c*dの最大公約数の倍数
  cnt_cd = b/((c*d)/gcd(c, d)) - (a-1)/((c*d)/gcd(c, d));
  // 包含と排除の原理
  cout << (b-a+1) - (cnt_c + cnt_d - cnt_cd) << endl;
}