結果

問題 No.1036 Make One With GCD 2
ユーザー seriru13seriru13
提出日時 2020-04-25 10:33:30
言語 C++17
(gcc 12.3.0 + boost 1.83.0)
結果
TLE  
実行時間 -
コード長 1,823 bytes
コンパイル時間 2,208 ms
コンパイル使用メモリ 205,384 KB
実行使用メモリ 41,216 KB
最終ジャッジ日時 2024-04-24 19:14:21
合計ジャッジ時間 10,557 ms
ジャッジサーバーID
(参考情報)
judge3 / judge1
このコードへのチャレンジ
(要ログイン)

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 TLE -
testcase_01 -- -
testcase_02 -- -
testcase_03 -- -
testcase_04 -- -
testcase_05 -- -
testcase_06 -- -
testcase_07 -- -
testcase_08 -- -
testcase_09 -- -
testcase_10 -- -
testcase_11 -- -
testcase_12 -- -
testcase_13 -- -
testcase_14 -- -
testcase_15 -- -
testcase_16 -- -
testcase_17 -- -
testcase_18 -- -
testcase_19 -- -
testcase_20 -- -
testcase_21 -- -
testcase_22 -- -
testcase_23 -- -
testcase_24 -- -
testcase_25 -- -
testcase_26 -- -
testcase_27 -- -
testcase_28 -- -
testcase_29 -- -
testcase_30 -- -
testcase_31 -- -
testcase_32 -- -
testcase_33 -- -
testcase_34 -- -
testcase_35 -- -
testcase_36 -- -
testcase_37 -- -
testcase_38 -- -
testcase_39 -- -
testcase_40 -- -
testcase_41 -- -
testcase_42 -- -
testcase_43 -- -
testcase_44 -- -
権限があれば一括ダウンロードができます

ソースコード

diff #

#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
#define inf 10e17
#define rep(i,n) for(long long i=0; i<n; i++)
#define repr(i,n,m) for(long long i=m; i<n; i++)
#define mod 1000000007
#define sorti(x) sort(x.begin(), x.end())
#define sortd(x) sort(x.begin(), x.end(), std::greater<long long>())
#define debug(x) std::cerr << (x) << std::endl;
#define roll(x) for (auto&& itr : x) { cerr << (itr) << " "; }

template <class T> inline void chmax(T &ans, T t) { if (t > ans) ans = t;}
template <class T> inline void chmin(T &ans, T t) { if (t < ans) ans = t;}

// 最大公約数を求める(ユークリッドの互除法).
long long gcd (long long x, long long y) {
  if (y > x) swap(x,y);
  if (y == 0) return x;
  return gcd(x%y,y);
}

// 素因数分解
/*
 * [2]-> 5, [3] -> 5のとき N = 2^5 * 3^5
 */
template<typename T>
map<T, long long> factorize(T x) {
  map<T, long long> res;
  for (long long i = 2; i * i <= x; ++i) {
    while (x % i == 0) {
      x /= i;
      res[i] += 1;
    }
  }
  if (x != 1) res[x]++;
  return res;
}

int main() {
  ll n;
  cin >> n;
  vector<ll> a(n);
  vector<map<ll, ll>> fact(n);
  repr(i, n, 0) {
    cin >> a[i];
    fact[i] = factorize(a[i]);
  }

  int head = 0, tail = 0;
  ll total = a[0], ans = 0;
  map<ll, ll> mp;
  while (head != n) {
    auto f = factorize(a[head]); // a[head]の素因数
    if (a[head] == 1) ans += 1;
    for (auto num : f) { mp[num.first] += 1; }
    for (auto& num : mp) {
      if (num.second > 1) {
        ll dis = head - tail;
        ans += dis * (dis - 1) / 2;
        for (;; tail++) {
          for (auto it : fact[tail]) {
            mp[it.first] -= 1;
          }
          if (num.second == 1) break;
        }
      }
    }
    head++;
  }

  ans += (head - tail) * (head - tail - 1) / 2;
  cout << ans << endl;
}
0