C++の練習を兼ねて, AtCoder Beginner Contest 206 の 問題E (Divide Both) を解いてみた.
■感想.
1. 問題E は, 方針が見えなかったので, 解説を参考に, AC版に到達できたと思う.
2. 個人的には, 解説のロジックで計算できる点が, 非常に興味深く思った.
3. 引き続き, 時間を見つけて, 過去問の学習を進めていきたいと思う.
本家のサイト AtCoder Beginner Contest 206 解説 の 各リンク を ご覧下さい.
■C++版プログラム(問題E/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 |
// 解き直し. // https://atcoder.jp/contests/abc206/editorial/2099 // C++(GCC 9.2.1) #include <bits/stdc++.h> using namespace std; using LL = long long; using vi = vector<int>; #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 int a[1010101], b[1010101]; int main(){ // 1. 入力情報. int L, R; scanf("%d %d", &L, &R); // 2. 素数. vi p; repx(i, 2, 1010101) if(!a[i]) repex(j, i * 2, 1010101, i) ++a[j]; repx(i, 2, 1010101) if(!a[i]) p.pb(i); // 素数は, 同じ素因数が, 1回出現したと見る. repx(i, 2, 1010101) if(!a[i]) a[i] = 1; // 3. 同じ素因数を二つ以上含まない整数は? for(auto &x : p){ int cur = x * x; if(cur >= 1010101) break; repex(i, cur, 1010101, cur) ++b[i]; } // 4. 互いに素でない整数の組. LL ans = 0; repx(k, 2, R + 1){ if(b[k]) continue; LL A = (LL)((R / k) - (L - 1) / k); ans += A * (A - 1) / 2 * ((a[k] & 1) ? +1 : -1); } // 5. x = g を 減算. repx(g, max(2, L), R + 1) ans -= (R / g - 1); // 6. 出力. printf("%lld\n", ans * 2); 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 |
[入力例] 3 7 [出力例] 2 ※AtCoderテストケースより [入力例] 4 10 [出力例] 12 ※AtCoderテストケースより [入力例] 1 1000000 [出力例] 392047955148 ※AtCoderテストケースより [入力例] 5 12 [出力例] 14 [入力例] 10 25 [出力例] 78 [入力例] 123 321 [出力例] 15202 [入力例] 2023 3202 [出力例] 545052 [入力例] 120205 690315 [出力例] 127432667154 |