AtCoder Beginner Contest 131 C

コード

#include<iostream>
using namespace std;

int gcd(int a, int b) {
  if (a < b) {
    int tmp = a; a = b; b = tmp;
  }
  int r = a % b;
  while (r != 0) {
    a = b;
    b = r;
    r = a % b;
  }
  return b;
}

long lcm(long a, long b) {
  return a * b / gcd(a, b);
}

int main() {
  long a, b;
  int c, d;
  cin >> a >> b >> c >> d;
  long div_c   = b/c        - (a-1)/c;
  long div_d   = b/d        - (a-1)/d;
  long div_lcm = b/lcm(c,d) - (a-1)/lcm(c,d);

  cout << (b-a+1) - (div_c + div_d - div_lcm) << endl;
}

学んだこと

C++17ではnumericライブラリにstd::lcmなどが用意されている。
- が、AtCoderで選択できるのはC++14なので、lcmなど自作する必要がある。
int型は10*9くらいまでしか表せない。もっと大きい整数を表現するにはlong型を使う。
- デバッグして突然負の値が登場してたら、型から値が溢れていることを疑うべし。