#470866 (C++17) No.1036 Make One With GCD 2

提出ソース

結果

問題	No.1036 Make One With GCD 2
ユーザー	rsk0315
提出日時	2020-04-25 20:40:46
言語	C++17 (gcc 12.3.0 + boost 1.83.0)
結果	TLE
実行時間	-
コード長	6,425 bytes
コンパイル時間	827 ms
コンパイル使用メモリ	63,764 KB
実行使用メモリ	82,120 KB
最終ジャッジ日時	2024-11-07 19:23:58
合計ジャッジ時間	28,324 ms
ジャッジサーバーID （参考情報）	judge2 / judge1

このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示

入力	結果	実行時間実行使用メモリ
testcase_00	AC	494 ms 82,120 KB
testcase_01	AC	484 ms 76,924 KB
testcase_02	AC	248 ms 76,880 KB
testcase_03	AC	151 ms 28,172 KB
testcase_04	AC	277 ms 49,692 KB
testcase_05	AC	2 ms 5,248 KB
testcase_06	AC	2 ms 5,248 KB
testcase_07	AC	191 ms 32,448 KB
testcase_08	AC	153 ms 26,600 KB
testcase_09	AC	603 ms 75,164 KB
testcase_10	AC	559 ms 69,764 KB
testcase_11	AC	618 ms 76,628 KB
testcase_12	AC	575 ms 70,468 KB
testcase_13	AC	743 ms 73,176 KB
testcase_14	AC	758 ms 74,036 KB
testcase_15	AC	702 ms 69,336 KB
testcase_16	AC	710 ms 69,900 KB
testcase_17	AC	730 ms 72,168 KB
testcase_18	AC	3 ms 5,248 KB
testcase_19	AC	3 ms 5,248 KB
testcase_20	AC	4 ms 5,248 KB
testcase_21	AC	4 ms 5,248 KB
testcase_22	AC	692 ms 68,348 KB
testcase_23	AC	505 ms 49,988 KB
testcase_24	AC	720 ms 71,328 KB
testcase_25	AC	658 ms 64,788 KB
testcase_26	AC	689 ms 67,204 KB
testcase_27	AC	2 ms 5,248 KB
testcase_28	AC	2 ms 5,248 KB
testcase_29	AC	2 ms 5,248 KB
testcase_30	AC	2 ms 5,248 KB
testcase_31	AC	2 ms 5,248 KB
testcase_32	AC	2 ms 5,248 KB
testcase_33	AC	2 ms 5,248 KB
testcase_34	AC	2 ms 5,248 KB
testcase_35	AC	2 ms 5,248 KB
testcase_36	AC	2 ms 5,248 KB
testcase_37	AC	2 ms 5,248 KB
testcase_38	AC	242 ms 76,876 KB
testcase_39	AC	520 ms 76,876 KB
testcase_40	AC	502 ms 49,988 KB
testcase_41	TLE	-
testcase_42	TLE	-
testcase_43	TLE	-
testcase_44	TLE	-

権限があれば一括ダウンロードができます

ソースコード

raw source code

#line 1 "test/yc_1036_sparse_table.test.cpp"
#define PROBLEM "https://yukicoder.me/problems/no/1036"

#include <cstdint>
#include <cstdio>
#include <algorithm>
#include <vector>

#line 1 "DataStructure/sparse_table.cpp"



/**
 * @brief sparse table
 * @author えびちゃん
 */

#include <cstddef>
#line 11 "DataStructure/sparse_table.cpp"

#line 1 "utility/literals.cpp"



/**
 * @brief ユーザ定義リテラル
 * @author えびちゃん
 */

#line 11 "utility/literals.cpp"

constexpr intmax_t  operator ""_jd(unsigned long long n) { return n; }
constexpr uintmax_t operator ""_ju(unsigned long long n) { return n; }
constexpr size_t    operator ""_zu(unsigned long long n) { return n; }
constexpr ptrdiff_t operator ""_td(unsigned long long n) { return n; }


#line 1 "integer/bit.cpp"



/** 
 * @brief ビット演算
 * @author えびちゃん
 */

// XXX integral promotion 関連の注意をあまりしていません

#include <climits>
#include <type_traits>

template <typename Tp>
constexpr auto countl_zero(Tp n)
  -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
  using value_type = typename std::make_unsigned<Tp>::type;
  int bits = (sizeof(value_type) * CHAR_BIT);
  if (n == 0) return bits;
  int res = 0;
  for (int i = bits / 2; i > 0; i /= 2) {
    value_type mask = ((static_cast<value_type>(1) << i) - 1) << i;
    if (n & mask) n >>= i;
    else res += i;
  }
  return res;
}
template <typename Tp>
constexpr auto countl_one(Tp n)
  -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
  using value_type = typename std::make_unsigned<Tp>::type;
  return countl_zero(static_cast<value_type>(~n));
}

template <typename Tp>
constexpr auto countr_zero(Tp n)
  -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
  using value_type = typename std::make_unsigned<Tp>::type;
  int bits = (sizeof(value_type) * CHAR_BIT);
  if (n == 0) return bits;
  int res = 0;
  for (int i = bits / 2; i > 0; i /= 2) {
    value_type mask = ((static_cast<value_type>(1) << i) - 1);
    if (!(n & mask)) res += i, n >>= i;
  }
  return res;
}
template <typename Tp>
constexpr auto countr_one(Tp n)
  -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
  using value_type = typename std::make_unsigned<Tp>::type;
  return countr_zero(static_cast<value_type>(~n));
}

constexpr unsigned long long half_mask[] = {
  0x5555555555555555uLL, 0x3333333333333333uLL, 0x0F0F0F0F0F0F0F0FuLL,
  0x00FF00FF00FF00FFuLL, 0x0000FFFF0000FFFFuLL, 0x00000000FFFFFFFFuLL
};

template <typename Tp>
constexpr auto popcount(Tp n)
  -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{
  int bits = static_cast<int>((sizeof n) * CHAR_BIT);
  for (int i = 0, j = 1; j < bits; ++i, j *= 2) {
    if (j <= 8) n = (n & half_mask[i]) + ((n >> j) & half_mask[i]);
    else n += n >> j;
  }
  return n & 0xFF;
}

template <typename Tp>
constexpr auto parity(Tp n)
  -> typename std::enable_if<std::is_unsigned<Tp>::value, int>::type
{ return popcount(n) & 1; }


template <typename Tp>
int clz(Tp n) { return countl_zero(static_cast<typename std::make_unsigned<Tp>::type>(n)); }
template <typename Tp>
int ctz(Tp n) { return countr_zero(static_cast<typename std::make_unsigned<Tp>::type>(n)); }

template <typename Tp>
int ilog2(Tp n) {
  return (CHAR_BIT * sizeof(Tp) - 1) - clz(static_cast<typename std::make_unsigned<Tp>::type>(n));
}
template <typename Tp>
bool is_pow2(Tp n) { return (n > 0) && ((n & (n-1)) == 0); }
template <typename Tp>
Tp floor2(Tp n) { return is_pow2(n)? n: static_cast<Tp>(1) << ilog2(n); }
template <typename Tp>
Tp ceil2(Tp n) { return is_pow2(n)? n: static_cast<Tp>(2) << ilog2(n); }

template <typename Tp>
constexpr auto reverse(Tp n)
  -> typename std::enable_if<std::is_unsigned<Tp>::value, Tp>::type
{
  int bits = static_cast<int>((sizeof n) * CHAR_BIT);
  for (int i = 0, j = 1; j < bits; ++i, j *= 2) {
    n = ((n & half_mask[i]) << j) | ((n >> j) & half_mask[i]);
  }
  return n;
}


#line 14 "DataStructure/sparse_table.cpp"

template <typename Band>
class sparse_table {
public:
  using size_type = size_t;
  using value_type = Band;

private:
  std::vector<std::vector<value_type>> M_c;

public:
  sparse_table() = default;

  template <typename InputIt>
  sparse_table(InputIt first, InputIt last) {
    assign(first, last);
  }
  template <typename InputIt>
  sparse_table(std::initializer_list<value_type> il) {
    assign(il.begin(), il.end());
  }

  template <typename InputIt>
  void assign(InputIt first, InputIt last) {
    M_c.assign(1, std::vector<value_type>(first, last));
    size_type n = M_c[0].size();
    for (size_type i = 1, ii = 1; M_c.back().size() > ii; (++i, ii <<= 1)) {
      M_c.emplace_back();
      M_c.back().reserve(n - ii);
      for (size_type j = ii; j < M_c[i-1].size(); ++j)
        M_c[i].push_back(M_c[i-1][j] + M_c[i-1][j-ii]);
    }
  }

  void assign(std::initializer_list<value_type> il) {
    assign(il.begin(), il.end());
  }

  value_type fold(size_type l, size_type r) const {
    size_type e = ilog2(r-l);
    r -= (1_zu << e) - 1;
    return M_c[e][l] + M_c[e][r-1];
  }
};


#line 9 "test/yc_1036_sparse_table.test.cpp"

template <typename Tp>
class gcd_monoid {
public:
  using value_type = Tp;

private:
  value_type M_x = 0;

  static value_type S_gcd(value_type x, value_type y) {
    while (y) std::swap(x %= y, y);
    return x;
  }

public:
  gcd_monoid() = default;  // identity

  gcd_monoid(value_type const& x): M_x(x) {}

  gcd_monoid& operator +=(gcd_monoid const& that) {
    M_x = S_gcd(M_x, that.M_x);
    return *this;
  }
  friend bool operator ==(gcd_monoid const& lhs, gcd_monoid const& rhs) {
    return lhs.M_x == rhs.M_x;
  }

  friend gcd_monoid operator +(gcd_monoid lhs, gcd_monoid const& rhs) { return lhs += rhs; }
  friend bool operator !=(gcd_monoid const& lhs, gcd_monoid const& rhs) {
    return !(lhs == rhs);
  }

  value_type const& get() const { return M_x; }
};

int main() {
  size_t n;
  scanf("%zu", &n);

  std::vector<intmax_t> a(n);
  for (auto& ai: a) scanf("%jd", &ai);

  sparse_table<gcd_monoid<intmax_t>> st(a.begin(), a.end());

  intmax_t res = 0;
  for (size_t i = 0; i < n; ++i) {
    if (st.fold(i, n).get() > 1) break;
    size_t lb = i, ub = n;
    while (ub-lb > 1) {
      size_t mid = (lb+ub) / 2;
      ((st.fold(i, mid).get() > 1)? lb: ub) = mid;
    }
    res += n-lb;
  }

  printf("%jd\n", res);
}