[AtCoder] ABC 142 D – Disjoint Set of Common Divisors

2019年9月30日

問題

方針

\( A \) と \( B \) の公約数を考えるので、\( A \) と \( B \) の最大公約数を考えます。最大公約数を素因数の数が求める答えとなります。

コード

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;

// 最大公約数
ll gcd(ll m, ll n) {
  if (n == 0) return m;
  else return gcd(n, m % n);
}

int main() {
  ll A, B;
  cin >> A >> B;
  ll m = min(A, B);
  int cnt = 1;
  ll g = gcd(A, B);
  ll t = g;
  for (ll i = 2; i * i <= t; i++) {
    if (g % i == 0) cnt++;
    while (g % i == 0) {
      g /= i;
    }
  }
  if (g != 1) cnt++;
  cout << cnt << "\n";

  return 0;
}