最大公約数・最小公倍数・素因数分解

Contents

最大公約数

ユークリッドの互除法を用いて求めます。

#define ll long long

// Greatest Common Divisor (最大公約数)
ll gcd(ll a, ll b) {
  // Eucledean algorithm
  while (a) {
    if (a < b) {
      std::swap(a, b);
    }
    a %= b;
  }
  return b;
}

※C++17以降はstd::gcdを用いることができます。C++14でも、GCCを使用している場合は__gcdを使用することができます。
AtCoderのC++はC++17になり、std::gcdが使えるようになりました。

最小公倍数

ab = gcd(a,b) * lcm(a,b)
⇔ lcm(a,b) = ab / gcd(a,b)

割り算を先に行ったほうが安全です。(オーバーフロー対策)

// Least Common Multiple
ll lcm(ll a, ll b) {
  return a / gcd(a, b) * b;
}

※C++17以降はstd::lcmを用いることができます。

素数判定

2, 3以降の素数は6で割ったときの余りが1または5、という特性を活かすと少しだけ高速化できます。
定数倍でしか早くならないですが…

bool is_prime(const unsigned n) {
  if (n % 2 == 0 || n % 3 == 0) {
    if (n == 2 || n == 3) {
      return true;
    }
    return false;
  }
  if (n == 1) {
    return false;
  }

  for (unsigned i = 5; i * i <= n; i += 6) {
    if (n % i == 0 || n % (i + 2) == 0) {
      return false;
    }
  }
  
  return true;
}

エラトステネスの篩を使用すれば候補を絞る事ができますが、n > 10^8くらいにならないと効果が得られないらしいです。
競技プログラミング界隈では、かえって実行速度は落ちると思います。

素因数分解

素因数である可能性のある数をforで回してひたすら求めます。
ここでは簡単のためにやりませんが、 2, 3, 5, 7, …と2以外は奇数を数えたほうが少し高速化されます。

// prime factorization (素因数分解)
// key: value of prime factor
// value: number of prime factor
std::map<ll, ll> prime_factorization(ll n) {
  std::map<ll, ll> prime_factors;
  for (ll i = 2; i * i <= n; i++) {
    while (n % i == 0) {
      prime_factors[i]++;
      n /= i;
    }
  }
  if (n != 1)
    prime_factors[n] = 1;
  return prime_factors;
}

使い方

std::mapはstd::pair<const key, value>のコンテナで実装されています。

auto factors = prime_factorization(n);
for (auto it = factors.begin(); it != factors.end(); it++) {
  std::cout << it->first << " " << it->second << std::endl;
}

約数の個数

auto factors = prime_factorization(n);
ll num_divisor = 1;
for (auto it = factors.begin(); it != factors.end(); it++) {
  num_divisor *= it->second + 1;
}

関連問題

約数の列挙

using ll = long long;
using ld = long double;

// 約数リスト
vector<ll> get_divisors(const ll n) {
  vector<ll> divs;
  for (ll i = 1; i * i <= n; i++) {
    if (n % i == 0) {
      divs.push_back(i);
      if (i != n / i) {
        divs.push_back(n / i);
      }
    }
  }

  // 必要に応じてソート
  // sort(divs.begin(), divs.end());

  return divs;
}

コードは下記ページを参考に作成しました。

関連問題