TOKI Regular Open Contest #16 E問目 - Multiple Multiplication

Source

TOKI Regular Open Contest #16
問題文
Problemset (TOKI Regular Open Contest #16)

問題概要

省略

解法

省略

cLay（version 20201123-1）のコード

C++に変換後のコードはこちら

int N;
Arr1d<int> A, arr;
int ps, p[320];
vector<int> ind[1d5+1];
{
  Modint res = 1;
  ll r, t;
  rd(N,A(N));
  ps = Prime(320, p);

  rep(m,ps){
    arr.setN(N);
    rep(i,N) arr[i] = 0;
    rep(i,N){
      arr[i] = 0;
      while(A[i] % p[m] == 0) A[i] /= p[m], arr[i]++;
    }
    r = 0;
    rep(i,N) r += (ll)(i - arr.PrevGE(i)) * (arr.NextGT(i) - i) * arr[i];
    res *= Modint(p[m]) ** r;
  }

  rep(m,1d5+1) ind[m].push_back(-1);
  rep(i,N) if(A[i] > 1) ind[A[i]].push_back(i);
  rep(m,1d5+1) ind[m].push_back(N);
  rep(m,1d5+1) if(ind[m].size() > 2){
    r = (ll) N * (N+1) / 2;
    rep(i,1,ind[m].size()){
      ll t = ind[m][i] - ind[m][i-1];
      r -= t * (t-1) / 2;
    }
    res *= Modint(m) ** r;
  }

  wt(res);
}

Current time: 2024年04月20日05時11分56秒
Last modified: 2020年11月23日16時58分30秒 (by laycrs)
Tags: Competitive_Programming_Incomplete TOKI
トップページに戻る

Logged in as: unknown user (not login)