数学/osa_k 法
(test/math/osa_k.test.cpp)

• View this file on GitHub
• Last update: 2023-07-21 12:14:05+09:00
• Problem: https://atcoder.jp/contests/abc177/tasks/abc177_e

Depends on

• osa_k 法 (include/emthrm/math/osa_k.hpp)
• prime sieve (include/emthrm/math/prime_sieve.hpp)

Code

/*
 * @title 数学/osa_k 法
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/abc177/tasks/abc177_e
 */

#include <algorithm>
#include <iostream>
#include <ranges>
#include <utility>
#include <vector>

#include "emthrm/math/osa_k.hpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  const int max_a = *std::max_element(a.begin(), a.end());
  const emthrm::OsaK osa_k(max_a);
  std::vector<int> prime_factor(max_a + 1, 0);
  for (const int a_i : a) {
    // GCC 12 adopted P2415.
    const std::vector<std::pair<int, int>> pf = osa_k.query(a_i);
    for (const int prime : pf
    // for (const int prime : osa_k.query(a_i)
                         | std::views::transform(&std::pair<int, int>::first)) {
      ++prime_factor[prime];
    }
  }
  const int maximum =
      *std::max_element(prime_factor.begin(), prime_factor.end());
  if (maximum <= 1) {
    std::cout << "pairwise coprime\n";
  } else if (maximum == n) {
    std::cout << "not coprime\n";
  } else {
    std::cout << "setwise coprime\n";
  }
  return 0;
}

#line 1 "test/math/osa_k.test.cpp"
/*
 * @title 数学/osa_k 法
 *
 * verification-helper: IGNORE
 * verification-helper: PROBLEM https://atcoder.jp/contests/abc177/tasks/abc177_e
 */

#include <algorithm>
#include <iostream>
#include <ranges>
#include <utility>
#include <vector>

#line 1 "include/emthrm/math/osa_k.hpp"



#line 6 "include/emthrm/math/osa_k.hpp"

#line 1 "include/emthrm/math/prime_sieve.hpp"



#include <numeric>
#line 6 "include/emthrm/math/prime_sieve.hpp"

namespace emthrm {

template <bool GETS_ONLY_PRIME>
std::vector<int> prime_sieve(const int n) {
  std::vector<int> smallest_prime_factor(n + 1), prime;
  std::iota(smallest_prime_factor.begin(), smallest_prime_factor.end(), 0);
  for (int i = 2; i <= n; ++i) {
    if (smallest_prime_factor[i] == i) [[unlikely]] prime.emplace_back(i);
    for (const int p : prime) {
      if (i * p > n || p > smallest_prime_factor[i]) break;
      smallest_prime_factor[i * p] = p;
    }
  }
  return GETS_ONLY_PRIME ? prime : smallest_prime_factor;
}

}  // namespace emthrm


#line 8 "include/emthrm/math/osa_k.hpp"

namespace emthrm {

struct OsaK {
  const std::vector<int> smallest_prime_factor;

  explicit OsaK(const int n) : smallest_prime_factor(prime_sieve<false>(n)) {}

  std::vector<std::pair<int, int>> query(int n) const {
    std::vector<std::pair<int, int>> res;
    while (n > 1) {
      const int prime = smallest_prime_factor[n];
      int exponent = 0;
      for (; smallest_prime_factor[n] == prime; n /= prime) {
        ++exponent;
      }
      res.emplace_back(prime, exponent);
    }
    return res;
  }
};

}  // namespace emthrm


#line 15 "test/math/osa_k.test.cpp"

int main() {
  int n;
  std::cin >> n;
  std::vector<int> a(n);
  for (int i = 0; i < n; ++i) {
    std::cin >> a[i];
  }
  const int max_a = *std::max_element(a.begin(), a.end());
  const emthrm::OsaK osa_k(max_a);
  std::vector<int> prime_factor(max_a + 1, 0);
  for (const int a_i : a) {
    // GCC 12 adopted P2415.
    const std::vector<std::pair<int, int>> pf = osa_k.query(a_i);
    for (const int prime : pf
    // for (const int prime : osa_k.query(a_i)
                         | std::views::transform(&std::pair<int, int>::first)) {
      ++prime_factor[prime];
    }
  }
  const int maximum =
      *std::max_element(prime_factor.begin(), prime_factor.end());
  if (maximum <= 1) {
    std::cout << "pairwise coprime\n";
  } else if (maximum == n) {
    std::cout << "not coprime\n";
  } else {
    std::cout << "setwise coprime\n";
  }
  return 0;
}

Back to top page