#402626 (C++14) No.937 Ultra Sword

提出ソース
結果

問題	No.937 Ultra Sword
コンテスト
ユーザー	noshi91
提出日時	2019-11-29 22:32:45
言語	C++14 (gcc 13.3.0 + boost 1.87.0)
結果	AC
実行時間	46 ms / 3,000 ms
コード長	6,613 bytes
コンパイル時間	695 ms
コンパイル使用メモリ	79,480 KB
実行使用メモリ	5,760 KB
最終ジャッジ日時	2024-11-18 08:28:55
合計ジャッジ時間	2,952 ms
ジャッジサーバーID （参考情報）	judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン	結果
other	AC * 47
権限があれば一括ダウンロードができます
ソースコード

raw source code
//#define NDEBUG
#include <algorithm>
#include <cstddef>
#include <cstdint>
#include <iostream>
#include <utility>
#include <vector>
#include <limits>
namespace n91 {

using i8 = std::int_fast8_t;
using i32 = std::int_fast32_t;
using i64 = std::int_fast64_t;
using u8 = std::uint_fast8_t;
using u32 = std::uint_fast32_t;
using u64 = std::uint_fast64_t;
using isize = std::ptrdiff_t;
using usize = std::size_t;

struct rep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { ++i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr rep(const usize f, const usize l) noexcept
      : f(std::min(f, l)), l(l) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return l; }
};
struct revrep {
  struct itr {
    usize i;
    constexpr itr(const usize i) noexcept : i(i) {}
    void operator++() noexcept { --i; }
    constexpr usize operator*() const noexcept { return i; }
    constexpr bool operator!=(const itr x) const noexcept { return i != x.i; }
  };
  const itr f, l;
  constexpr revrep(const usize f, const usize l) noexcept
      : f(l - 1), l(std::min(f, l) - 1) {}
  constexpr auto begin() const noexcept { return f; }
  constexpr auto end() const noexcept { return l; }
};
template <class T> auto md_vec(const usize n, const T &value) {
  return std::vector<T>(n, value);
}
template <class... Args> auto md_vec(const usize n, Args... args) {
  return std::vector<decltype(md_vec(args...))>(n, md_vec(args...));
}
template <class T> constexpr T difference(const T &a, const T &b) noexcept {
  if (a < b) {
    return b - a;
  } else {
    return a - b;
  }
}
template <class T> void chmin(T &a, const T &b) noexcept {
  if (b < a) {
    a = b;
  }
}
template <class T> void chmax(T &a, const T &b) noexcept {
  if (a < b) {
    a = b;
  }
}
template <class F> class fix_point : private F {
public:
  explicit constexpr fix_point(F &&f) : F(std::forward<F>(f)) {}

  template <class... Args>
  constexpr decltype(auto) operator()(Args &&... args) const {
    return F::operator()(*this, std::forward<Args>(args)...);
  }
};
template <class F> constexpr decltype(auto) make_fix(F &&f) {
  return fix_point<F>(std::forward<F>(f));
}
template <class T> T scan() {
  T ret;
  std::cin >> ret;
  return ret;
}

} // namespace n91

#include <cassert>
#include <cstddef>
#include <numeric>
#include <utility>
#include <vector>

namespace n91 {

class prime_sieve {
public:
  using size_type = std::size_t;

private:
  std::vector<size_type> prime, factor;

public:
  prime_sieve() {}
  explicit prime_sieve(const size_type size) : prime(), factor(size) {
    if (size == 0) {
      return;
    }
    std::iota(factor.begin(), factor.end(), static_cast<size_type>(0));
    factor[0] = 1;
    if (size == 1) {
      return;
    }
    factor[1] = 0;
    prime.reserve(size);
    for (size_type i{2}; i != size; ++i) {
      const size_type fi{factor[i]};
      if (fi == i) {
        prime.push_back(i);
      }
      for (const size_type p : prime) {
        if (p > fi) {
          break;
        }
        const size_type ip{i * p};
        if (ip >= size) {
          break;
        }
        factor[ip] = p;
      }
    }
    prime.shrink_to_fit();
  }
  size_type len() const noexcept { return factor.size(); }
  bool is_prime(const size_type i) const noexcept {
    assert(i < len());
    return factor[i] == i;
  }
  std::vector<size_type> factorize(size_type i) const noexcept {
    assert(i != 0);
    std::vector<size_type> ret;
    while (i != 1) {
      ret.push_back(factor[i]);
      i /= factor[i];
    }
    return std::move(ret);
  }
  template <class C> void divisor_zeta(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{1}; j * prime[i] < n; ++j) {
        c[j * prime[i]] += c[j];
      }
    }
  }
  template <class C> void divisor_mobius(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{(n - 1) / prime[i]}; j != 0; --j) {
        c[j * prime[i]] -= c[j];
      }
    }
  }
  template <class C> void multiple_zeta(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{(n - 1) / prime[i]}; j != 0; --j) {
        c[j] += c[j * prime[i]];
      }
    }
  }
  template <class C> void multiple_mobius(C &c) const noexcept {
    const size_type n{c.size()};
    assert(n <= len());
    for (size_type i{0}; i != prime.size() && prime[i] < n; ++i) {
      for (size_type j{1}; j * prime[i] < n; ++j) {
        c[j] -= c[j * prime[i]];
      }
    }
  }
};

} // namespace n91

#include <algorithm>
#include <iostream>
#include <utility>

namespace n91 {

void main_() {
  /*
  std::ios::sync_with_stdio(false);
  std::cin.tie(nullptr);
  //*/
  const usize n = scan<usize>();
  std::vector<usize> a(n);
  for (auto &e : a) {
    std::cin >> e;
  }
  const usize am = *std::max_element(a.cbegin(), a.cend()) + 1;

  const auto get = [](const usize a, const usize i) -> bool {
    return a >> i & 1;
  };

  const auto gcd = [get](usize a, usize b) {
    for (const usize i : revrep(0, 17)) {
      if (a < b) {
        std::swap(a, b);
      }
      if (get(b, i)) {
        b ^= a;
      }
      if (b == 0) {
        return a;
      }
      if (get(a, i)) {
        usize t = b;
        while (!get(t, i)) {
          t *= 2;
        }
        a ^= t;
      }
    }
    assert(false);
  };

  usize g = 0;
  for (const auto e : a) {
    g = gcd(g, e);
  }

  const auto ok = [g, get](usize a) {
    for (const usize i : revrep(0, 17)) {
      if (get(a, i)) {
        usize t = g;
        while (!get(t, i)) {
          t *= 2;
        }
        a ^= t;
      }
      if (get(g, i)) {
        return a == 0;
      }
    }
    assert(false);
  };

  const prime_sieve ps(am);
  std::vector<u64> rev(am);
  for (const auto e : a) {
    rev[e] += e;
  }
  ps.multiple_zeta(rev);
  const u64 sum = std::accumulate(a.cbegin(), a.cend(), static_cast<u64>(0));
  u64 ans = std::numeric_limits<u64>::max();
  for (const usize i : rep(1, am)) {
    if (ok(i)) {
      chmin(ans, sum - rev[i] + rev[i] / i);
    }
  }
  std::cout << ans << std::endl;
}

} // namespace n91

int main() {
  n91::main_();
  return 0;
}
yukicoder

結果

ソースコード
