DNEK's blog

Sounds like "dee-neck". 「でぃーねっく」と読みます。

AtCoder「Coprime」をGCDを使わずちょっとだけ楽（？）に解く

競技プログラミング

前置き

AtCoder Beginner Contest 177 E「Coprime」をほんのちょっとだけ楽（？）に解くという話です。

自明orどうでもいいからかもしれませんが、同様の指摘をしている記事がすぐには見当たらなかったので書いておきます。

atcoder.jp

公式解説はこちらです。 https://atcoder.jp/contests/abc177/editorial/82

解法

基本的には↑の公式解説の通りで、setwiseとpairwiseそれぞれについてGCDと高速素因数分解で解くのが比較的楽だと思います。

しかし私はこの単純なGCDの処理を書くのさえ面倒だと思う人間なので（？）、両方とも高速素因数分解を用いて判定しました。

まず、pairwiseについては公式解説の通り、各素因数に重複が無いかを知りたいです。 このためには、setやbool配列などで出現済みの素因数を保持しておいて再度出現したらbreakすれば十分なのですが、今回はmapやint配列でそれぞれの素因数の出現回数を一通り数え上げます。 その結果、どの素因数の出現回数も1回以下であれば良いです。

次にsetwiseですが、 A 全体のGCDを取るということは、ある素数 p について一度でも因数に持っていない A_i が出てくればその時点でGCDは p を持たなくなります。 対偶を言えば、全体のGCDが p を持っているならば、すべての A_i が p を持っていることになります。 つまり、pairwiseのときに使った出現回数について、どれも N 回未満であればsetwiseです。

というわけで、以下のように高速素因数分解のライブラリを貼り付ける以外はちょっとだけシンプルに書けるようになりました。

atcoder.jp

#include <bits/stdc++.h>
#define each(i, a) for (auto &&i : (a))
using namespace std;

using vi = vector<int>;
using seti = set<int>;

template <class T>
void COUT(const T &x) { cout << x << endl; }

struct prime_factors_osa_k {
  vi spf; // smallest prime factor
  prime_factors_osa_k(int n): spf(n + 1) {
    spf[1] = 1;
    for (int i = 0; i <= n; i++) spf[i] = i;
    for (int i = 2; i * i <= n; i++) if (spf[i] == i)
      for (int j = i * i; j <= n; j += i)
        if (spf[j] == j) spf[j] = i;
  }
  seti operator()(int x) {
    seti ret;
    while (x != 1) {
      ret.insert(spf[x]);
      x = x / spf[x];
    }
    return ret;
  }
} prime_factors(1000000);

int main() {
  int N;
  cin >> N;
  vi A(N);
  each(x, A) cin >> x;

  vi cnt(1000001);
  each(x, A) each(f, prime_factors(x)) cnt[f]++;
  int mx = 1;
  each(x, cnt) if (mx < x) mx = x;

  if (mx == 1) COUT("pairwise coprime");
  else if (mx < N) COUT("setwise coprime");
  else COUT("not coprime");
}

実は今回のコンテストまで高速素因数分解を知らなかったので、コンテスト中は「prime factorization table」とかでググって出てきた以下の記事を参考に実装しました。

www.geeksforgeeks.org

↑に書いた prime_factors_osa_k は、コンテスト後に書き直したものです。 osa_k法と呼ばれているのはコンテスト後に知りました。

ちなみに今回は問題の性質上setを使っていますが、用途に応じてvectorやmapに書き換えると良いでしょう。

終わりに

Eまで30分で解いて1804パフォでした。 早く6完したい。

追記

投稿してからTwitterで軽く検索したら普通に言及されてました（それはそう）。

hitoare.hatenablog.com