結果
問題 | No.2046 Ans Mod? Mod Ans! |
ユーザー |
|
提出日時 | 2022-08-19 22:14:59 |
言語 | C++17 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 37 ms / 4,000 ms |
コード長 | 2,349 bytes |
コンパイル時間 | 1,892 ms |
コンパイル使用メモリ | 196,904 KB |
最終ジャッジ日時 | 2025-01-31 01:15:33 |
ジャッジサーバーID (参考情報) |
judge4 / judge4 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 18 |
ソースコード
#include <bits/stdc++.h>#include <random>using namespace std;//#include <atcoder/all>//using namespace atcoder;using ll = long long;using vll = vector<ll>;using vvll = vector<vll>;using vvvll = vector<vvll>;using vvvvll = vector<vvvll>;using vvvvvll = vector<vvvvll>;using vvvvvvll = vector<vvvvvll>;using vb = vector<bool>;using vvb = vector<vb>;using vvvb = vector<vvb>;using vvvvb = vector<vvvb>;using vd = vector<double>;using vvd = vector<vd>;using vvvd = vector<vvd>;using vvvvd = vector<vvvd>;using vvvvvd = vector<vvvvd>;#define all(A) A.begin(),A.end()#define ALL(A) A.begin(),A.end()#define rep(i, n) for (ll i = 0; i < (ll) (n); i++)using pqr = priority_queue<pair<ll, ll>, vector<pair<ll, ll>>, greater<pair<ll, ll>>>;template<class T>bool chmax(T& p, T q, bool C = 1) {if (C == 0 && p == q) {return 1;}if (p < q) {p = q;return 1;}else {return 0;}}template<class T>bool chmin(T& p, T q, bool C = 1) {if (C == 0 && p == q) {return 1;}if (p > q) {p = q;return 1;}else {return 0;}}ll gcd(ll(a), ll(b)) {if (b == 0)return a;ll c = a;while (a % b != 0) {c = a % b;a = b;b = c;}return b;}ll mod = 1e9 + 7;ll modPow(long long a, long long n, long long p = mod) {if (n == 0) return 1; // 0乗にも対応する場合if (n == 1) return a % p;if (n % 2 == 1) return (a * modPow(a, n - 1, p)) % p;long long t = modPow(a, n / 2, p);return (t * t) % p;}int main() {cin.tie(nullptr);ios::sync_with_stdio(false);ll M = 2e5 + 1;ll N;cin >> N;vll R(M + 1, 0);vll A(N);rep(i, N) {cin >> A[i];R[A[i]] = 1;}ll an = 0;vll SR(M + 2, 0), SN(M + 2, 0);for (ll m = M; m > 0; m--) {SR[m] = SR[m + 1];SN[m] = SN[m + 1];if (R[m] == 1) {an += m * SN[m + 1];for (ll j = m; j <= M; j += m) {ll nj = min(j + m, M + 1);ll s = SR[j] - SR[nj];ll n = SN[j] - SN[nj];ll p = j * n;an -= (s - p);}SR[m] += m;SN[m] += 1;}}cout << an << endl;}