結果

問題 No.1036 Make One With GCD 2
コンテスト
ユーザー seriru13
提出日時 2020-04-25 10:33:30
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 1,823 bytes
コンパイル時間 2,891 ms
コンパイル使用メモリ 203,952 KB
最終ジャッジ日時 2025-01-10 00:58:36
ジャッジサーバーID
（参考情報） 		judge3 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 2 WA * 2
other AC * 1 WA * 12 TLE * 28
権限があれば一括ダウンロードができます

ソースコード

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