AtCoder Grand Contest 038 C問題 - LCMs

Source

AtCoder Grand Contest 038
問題文

問題概要

省略

解法

省略

cLay（version 20190921-1）のコード

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

#define MD 998244353

int cnt[1000001];
mint c[1000001];

{
  mint res = 0, s, t;

  rep(i,1,1000001) c[i] = (mint) 1 / i;
  rep(i,1,1000001) rep(j,2i,1000001,i) c[j] -= c[i];

  REP(rd_int()) cnt[rd_int()]++;
  rep(i,1,1000001){
    s = t = 0;
    rep(j,i,1000001,i) if(cnt[j]) s += (mint) j * cnt[j];
    rep(j,i,1000001,i) if(cnt[j]) t += s * j * cnt[j];
    res += c[i] * t;
  }

  rep(i,1,1000001) if(cnt[i]) res -= (mint) i * cnt[i];
  res /= 2;

  wt(res);
}

Current time: 2024年04月26日04時33分30秒
Last modified: 2019年09月22日00時26分09秒 (by laycrs)
Tags: Competitive_Programming_Incomplete AtCoder AtCoder_Grand_Contest AGC038 AGC_C
トップページに戻る

Logged in as: unknown user (not login)

ログイン：