k-tokitoh

2019-07-28

AtCoder Beginner Contest 131 C

C - Anti-Division

コード

#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 などが用意されている。
  • が、C++14 なので、lcm など自作する必要がある。
• int 型は 10*9 くらいまでしか表せない。もっと大きい整数を表現するには long 型を使う。
  • デバッグして突然負の値が登場してたら、型から値が溢れていることを疑うべし。