C++の練習を兼ねて, AtCoder Grand Contest 038 の 問題C (LCMs) を解いてみた.
■感想.
1. 問題Cは, 方針が見えなかったので, 解説を参考に提出して, ようやく, AC版に到達出来た.
2. 解説にあるように, 計算削減のために, 逆数を考える方針が, 個人的には, 非常に面白い問題に感じた.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Grand Contest 038 解説 を ご覧下さい.
■C++版プログラム(問題C／AC版).
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 96 97 98 99 100 |
// 解き直し. // https://img.atcoder.jp/agc038/editorial.pdf // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vl = vector<LL>; using vvl = vector<vl>; #define repex(i, a, b, c) for(int i = a; i < b; i += c) #define repx(i, a, b) repex(i, a, b, 1) #define rep(i, n) repx(i, 0, n) #define repr(i, a, b) for(int i = a; i >= b; i--) #define pb push_back const LL MOD = 998244353; LL a[202020], w[1010101], c[1010101]; // Fermat's little theorem から, 大きな冪乗の計算を行う. // @param a: べき乗したい正整数. // @param b: 指数. // @return: べき乗した計算結果(mod版). LL mPow(LL a, LL b){ LL t = 1; while(b){ if(b & 1) t = (t * a) % MOD; a = a * a % MOD; b >>= 1; } return t % MOD; } int main(){ // 1. 入力情報. int N; scanf("%d", &N); rep(i, N){ scanf("%lld", &a[i]); c[(int)a[i]]++; // a[i] = x となる個数を保存. } // 2. w の 計算. vvl div(1010101); // a[i] を 約数ごとに分類. repx(i, 1, 1010101) w[i] = mPow((LL)i, MOD - 2LL); repx(i, 1, 1010101){ vl v; repex(j, i, 1010101, i){ if(j % i == 0){ if(j > i){ w[j] += MOD - w[i]; w[j] %= MOD; } if(c[j]) rep(k, c[j]) v.pb((LL)j); } } div[i] = v; } // ex. // w[1] = +1 // w[2] = -1 / 2 = 499122176 // w[3] = -2 / 3 = 332748117 // w[4] = -1 / 4 = 249561088 // w[5] = -4 / 5 = 598946611 // w[6] = +1 / 3 = 332748118 // ... // w[10] = +2 / 5 = 199648871 // w[11] = -10 / 11 = 272248459 // w[12] = +1 / 6 = 166374059 // ... // repx(i, 1, 13) printf("%lld ", w[i]); // 3. 解説上の数式を計算(Σw[d]Σ(a[i] * a[j])). LL ans = 0; repx(d, 1, 1010101){ if(div[d].size()){ // Σa[i] * a[j] の 計算準備. LL p = 0, q = 0; rep(i, div[d].size()){ p += div[d][i]; p %= MOD; q += div[d][i] * div[d][i]; q %= MOD; } // Σa[i] * a[j] を 計算. // -> {(a1 + a2 + ... + ak) * (a1 + a2 + ... + ak) - a1 の 2乗 - ... - ak の 2乗} ÷ 2 で 計算. LL t = (p * p + MOD - q) % MOD; t *= mPow(2LL, MOD - 2LL); t %= MOD; // w[d] を 反映. ans += t * w[d]; ans %= MOD; } } // 4. 出力. printf("%lld\n", ans); return 0; } |
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 |
[入力例] 3 2 4 6 [出力例] 22 ※AtCoderテストケースより [入力例] 8 1 2 3 4 6 8 12 12 [出力例] 313 ※AtCoderテストケースより [入力例] 10 356822 296174 484500 710640 518322 888250 259161 609120 592348 713644 [出力例] 353891724 ※AtCoderテストケースより [入力例] 5 1 2 12 16 18 [出力例] 322 [入力例] 12 2 4 8 18 24 36 48 52 60 64 72 84 [出力例] 15514 [入力例] 20 116 102 98 87 71 105 13 107 34 20 58 117 71 50 27 12 112 118 9 103 [出力例] 726127 [入力例] 50 3638 3573 884 2825 2621 3228 1807 82 3798 2285 358 4277 998 392 2300 3708 4132 4314 3414 363 233 61 1480 3895 4218 2576 3651 3763 4258 1270 135 2566 3098 2900 2407 729 1301 4215 2568 51 1528 2287 410 2305 3707 911 2417 1205 831 1501 [出力例] 518757047 |
■参照サイト
AtCoder Grand Contest 038