結果
問題 | No.1276 3枚のカード |
ユーザー | ecottea |
提出日時 | 2022-09-20 18:16:03 |
言語 | C++14 (gcc 12.3.0 + boost 1.83.0) |
結果 |
AC
|
実行時間 | 184 ms / 2,000 ms |
コード長 | 18,713 bytes |
コンパイル時間 | 4,505 ms |
コンパイル使用メモリ | 247,780 KB |
実行使用メモリ | 9,120 KB |
最終ジャッジ日時 | 2023-08-23 19:37:40 |
合計ジャッジ時間 | 12,584 ms |
ジャッジサーバーID (参考情報) |
judge15 / judge11 |
(要ログイン)
テストケース
テストケース表示入力 | 結果 | 実行時間 実行使用メモリ |
---|---|---|
testcase_00 | AC | 1 ms
4,376 KB |
testcase_01 | AC | 1 ms
4,380 KB |
testcase_02 | AC | 1 ms
4,376 KB |
testcase_03 | AC | 2 ms
4,380 KB |
testcase_04 | AC | 2 ms
4,376 KB |
testcase_05 | AC | 2 ms
4,380 KB |
testcase_06 | AC | 1 ms
4,376 KB |
testcase_07 | AC | 2 ms
4,380 KB |
testcase_08 | AC | 1 ms
4,380 KB |
testcase_09 | AC | 1 ms
4,376 KB |
testcase_10 | AC | 160 ms
8,264 KB |
testcase_11 | AC | 83 ms
5,728 KB |
testcase_12 | AC | 103 ms
6,016 KB |
testcase_13 | AC | 107 ms
5,944 KB |
testcase_14 | AC | 13 ms
4,380 KB |
testcase_15 | AC | 88 ms
5,820 KB |
testcase_16 | AC | 172 ms
8,040 KB |
testcase_17 | AC | 100 ms
5,952 KB |
testcase_18 | AC | 78 ms
5,824 KB |
testcase_19 | AC | 120 ms
6,356 KB |
testcase_20 | AC | 74 ms
5,660 KB |
testcase_21 | AC | 77 ms
5,680 KB |
testcase_22 | AC | 174 ms
8,344 KB |
testcase_23 | AC | 13 ms
4,376 KB |
testcase_24 | AC | 115 ms
5,936 KB |
testcase_25 | AC | 45 ms
4,628 KB |
testcase_26 | AC | 139 ms
8,500 KB |
testcase_27 | AC | 155 ms
8,196 KB |
testcase_28 | AC | 150 ms
8,596 KB |
testcase_29 | AC | 92 ms
5,684 KB |
testcase_30 | AC | 22 ms
4,380 KB |
testcase_31 | AC | 12 ms
4,376 KB |
testcase_32 | AC | 47 ms
4,604 KB |
testcase_33 | AC | 5 ms
4,376 KB |
testcase_34 | AC | 34 ms
4,508 KB |
testcase_35 | AC | 32 ms
4,420 KB |
testcase_36 | AC | 4 ms
4,380 KB |
testcase_37 | AC | 30 ms
4,500 KB |
testcase_38 | AC | 21 ms
4,380 KB |
testcase_39 | AC | 48 ms
4,768 KB |
testcase_40 | AC | 168 ms
8,200 KB |
testcase_41 | AC | 142 ms
8,536 KB |
testcase_42 | AC | 154 ms
7,928 KB |
testcase_43 | AC | 137 ms
7,792 KB |
testcase_44 | AC | 184 ms
8,432 KB |
testcase_45 | AC | 168 ms
8,832 KB |
testcase_46 | AC | 168 ms
8,924 KB |
testcase_47 | AC | 143 ms
7,792 KB |
testcase_48 | AC | 138 ms
8,536 KB |
testcase_49 | AC | 152 ms
8,452 KB |
testcase_50 | AC | 165 ms
8,660 KB |
testcase_51 | AC | 147 ms
7,924 KB |
testcase_52 | AC | 129 ms
7,852 KB |
testcase_53 | AC | 147 ms
7,836 KB |
testcase_54 | AC | 166 ms
8,124 KB |
testcase_55 | AC | 134 ms
9,120 KB |
testcase_56 | AC | 129 ms
8,924 KB |
testcase_57 | AC | 160 ms
8,120 KB |
testcase_58 | AC | 164 ms
8,200 KB |
testcase_59 | AC | 148 ms
7,844 KB |
testcase_60 | AC | 183 ms
8,340 KB |
ソースコード
#ifndef HIDDEN_IN_VS // 折りたたみ用 // 警告の抑制 #define _CRT_SECURE_NO_WARNINGS // ライブラリの読み込み #include <bits/stdc++.h> using namespace std; // 型名の短縮 using ll = long long; // -2^63 ~ 2^63 = 9 * 10^18(int は -2^31 ~ 2^31 = 2 * 10^9) using pii = pair<int, int>; using pll = pair<ll, ll>; using pil = pair<int, ll>; using pli = pair<ll, int>; using vi = vector<int>; using vvi = vector<vi>; using vvvi = vector<vvi>; using vl = vector<ll>; using vvl = vector<vl>; using vvvl = vector<vvl>; using vb = vector<bool>; using vvb = vector<vb>; using vvvb = vector<vvb>; using vc = vector<char>; using vvc = vector<vc>; using vvvc = vector<vvc>; using vd = vector<double>; using vvd = vector<vd>; using vvvd = vector<vvd>; template <class T> using priority_queue_rev = priority_queue<T, vector<T>, greater<T>>; using Graph = vvi; // 定数の定義 const double PI = acos(-1); const vi DX = { 1, 0, -1, 0 }; // 4 近傍(下,右,上,左) const vi DY = { 0, 1, 0, -1 }; int INF = 1001001001; ll INFL = 4004004004004004004LL; double EPS = 1e-12; // 入出力高速化 struct fast_io { fast_io() { cin.tie(nullptr); ios::sync_with_stdio(false); cout << fixed << setprecision(18); } } fastIOtmp; // 汎用マクロの定義 #define all(a) (a).begin(), (a).end() #define sz(x) ((int)(x).size()) #define lbpos(a, x) (int)distance((a).begin(), std::lower_bound(all(a), x)) #define ubpos(a, x) (int)distance((a).begin(), std::upper_bound(all(a), x)) #define Yes(b) {cout << ((b) ? "Yes\n" : "No\n");} #define rep(i, n) for(int i = 0, i##_len = int(n); i < i##_len; ++i) // 0 から n-1 まで昇順 #define repi(i, s, t) for(int i = int(s), i##_end = int(t); i <= i##_end; ++i) // s から t まで昇順 #define repir(i, s, t) for(int i = int(s), i##_end = int(t); i >= i##_end; --i) // s から t まで降順 #define repe(v, a) for(const auto& v : (a)) // a の全要素(変更不可能) #define repea(v, a) for(auto& v : (a)) // a の全要素(変更可能) #define repb(set, d) for(int set = 0; set < (1 << int(d)); ++set) // d ビット全探索(昇順) #define repp(a) sort(all(a)); for(bool a##_perm = true; a##_perm; a##_perm = next_permutation(all(a))) // a の順列全て(昇順) #define smod(n, m) ((((n) % (m)) + (m)) % (m)) // 非負mod #define uniq(a) {sort(all(a)); (a).erase(unique(all(a)), (a).end());} // 重複除去 #define EXIT(a) {cout << (a) << endl; exit(0);} // 強制終了 // 汎用関数の定義 template <class T> inline ll pow(T n, int k) { ll v = 1; rep(i, k) v *= n; return v; } template <class T> inline bool chmax(T& M, const T& x) { if (M < x) { M = x; return true; } return false; } // 最大値を更新(更新されたら true を返す) template <class T> inline bool chmin(T& m, const T& x) { if (m > x) { m = x; return true; } return false; } // 最小値を更新(更新されたら true を返す) // 演算子オーバーロード template <class T, class U> inline istream& operator>>(istream& is, pair<T, U>& p) { is >> p.first >> p.second; return is; } template <class T> inline istream& operator>>(istream& is, vector<T>& v) { repea(x, v) is >> x; return is; } template <class T> inline vector<T>& operator--(vector<T>& v) { repea(x, v) --x; return v; } template <class T> inline vector<T>& operator++(vector<T>& v) { repea(x, v) ++x; return v; } // 手元環境(Visual Studio) #ifdef _MSC_VER #include "local.hpp" // 提出用(gcc) #else inline int popcount(int n) { return __builtin_popcount(n); } inline int popcount(ll n) { return __builtin_popcountll(n); } inline int lsb(int n) { return n != 0 ? __builtin_ctz(n) : -1; } inline int lsb(ll n) { return n != 0 ? __builtin_ctzll(n) : -1; } inline int msb(int n) { return n != 0 ? (31 - __builtin_clz(n)) : -1; } inline int msb(ll n) { return n != 0 ? (63 - __builtin_clzll(n)) : -1; } #define gcd __gcd #define dump(...) #define dumpel(v) #define dump_list(v) #define input_from_file(f) #define output_to_file(f) #define Assert(b) { if (!(b)) while (1) cout << "OLE"; } #endif #endif // 折りたたみ用 //--------------AtCoder 専用-------------- #include <atcoder/all> using namespace atcoder; using mint = modint1000000007; //using mint = modint998244353; //using mint = modint; // mint::set_mod(m); istream& operator>>(istream& is, mint& x) { ll x_; is >> x_; x = x_; return is; } ostream& operator<<(ostream& os, const mint& x) { os << x.val(); return os; } using vm = vector<mint>; using vvm = vector<vm>; using vvvm = vector<vvm>; //---------------------------------------- // O(n^3) mint naive(ll n) { mint res = 0; repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) { if (b % a == 0 || a % b == 0 || c % b != 0 || b == c) continue; res++; } return res; } void zikken() { int N = 100; vm res(N + 1); repi(n, 1, N) { res[n] = naive(n); } dump_list(res); exit(0); } /* {0, 0, 0, 0, 1, 2, 7, 10, 18, 27, 41, 49, 76, 88, 112, 142, 178, 197, 249, 272, 334, 385, 434, 465, 567, 620, 682, 753, 854, 900, 1044, 1096, 1214, 1310, 1400, 1508, 1709, 1778, 1883, 2002, 2214, 2293, 2518, 2603, 2787, 2993, 3130, 3225, 3544, 3683, 3904, 4076, 4305, 4419, 4724, 4924, 5253, 5453, 5639, 5771, 6278, 6420, 6622, 6939, 7278, 7527, 7924, 8085, 8405, 8658, 9099, 9272, 9904, 10087, 10342, 10732, 11100, 11413, 11898, 12099, 12720, 13094, 13386, 13600, 14365, 14717, 15027, 15367, 15940, 16176, 17015, 17405, 17872, 18244, 18590, 18990, 19878, 20146, 20663, 21220, 21959} */ //【素数の列挙】O(n log(log n)) /* * n 以下の素数を列挙し,ps に昇順に格納する. */ void eratosthenes(int n, vi& ps) { // verify : https://algo-method.com/tasks/330 ps.clear(); // 素数かどうかを記録しておくためのテーブル vb is_prime(n + 1, true); is_prime[0] = is_prime[1] = false; int i = 2; // √n 以下の i の処理 for (; i <= n / i; i++) { if (is_prime[i]) { ps.push_back(i); for (int j = i * i; j <= n; j += i) is_prime[j] = false; } } // √n より大きい i の処理 for (; i <= n; i++) if (is_prime[i]) ps.push_back(i); } //【約数変換,LCM 畳込み】 /* * Divisor_transform<T>(int n) : O(n log(log n)) * n までの素数を持って初期化する. * * divisor_zeta(vT& a) : O(n log(log n)) * A[j] = Σ_(i | j) a[i] なる A に上書きする. * (約数ゼータ変換,倍数への累積和) * * divisor_mobius(vT& A) : O(n log(log n)) * A[j] = Σ_(i | j) a[i] なる a に上書きする. * (約数メビウス変換,約数への差分) * * vT lcm_convolution(vT a, vT b) : O(n log(log n)) * c[k] = Σ_(lcm(i, j) = k) a[i] b[j] なる c を返す. * ただし c[n] を含めそれ以降は切り捨てる. * * 制約:1-indexed とし,a[0], b[0] は使用しない. * * 利用:【素数の列挙】 */ template <typename T> struct Divisor_transform { // 参考 : https://qiita.com/convexineq/items/afc84dfb9ee4ec4a67d5 // verify : https://judge.yosupo.jp/problem/lcm_convolution vi ps; // 素数のリスト Divisor_transform() {} Divisor_transform(int n) { eratosthenes(n, ps); } void divisor_zeta(vector<T>& f) { // 具体例: // A[1] = a[1] // A[2] = a[1] + a[2] // A[3] = a[1] + a[3] // A[4] = a[1] + a[2] + a[4] // A[5] = a[1] + a[5] // A[6] = a[1] + a[2] + a[3] + a[6] // A[7] = a[1] + a[7] // A[8] = a[1] + a[2] + a[4] + a[8] int n = sz(f); // 各素因数ごとに下からの累積和をとる repe(p, ps) { repi(i, 1, (n - 1) / p) f[p * i] += f[i]; } } void divisor_mobius(vector<T>& f) { int n = sz(f); // 各素因数ごとに上からの差分をとる repe(p, ps) { repir(i, (n - 1) / p, 1) f[p * i] -= f[i]; } } vector<T> lcm_convolution(vector<T> a, vector<T> b) { int n = sz(a); // 各素因数の max をとったものが lcm なので max 畳込みを行う. divisor_zeta(a); divisor_zeta(b); rep(i, n) a[i] *= b[i]; divisor_mobius(a); return a; } }; //【約数関数 σ_k(n)】O(n log(log n)) /* * i = [1..n] について約数関数 σ_k(i) = (i の約数の k 乗和) を s[i] に格納する. * 特に k = 0 なら約数の個数,k = 1 なら約数の総和と等価である. * * 利用:【約数変換,LCM 畳込み】 */ template <class T> void divisor_sigma(int k, int n, vector<T>& s) { // 参考 : https://maspypy.com/%E6%95%B0%E5%AD%A6-%E7%95%B3%E3%81%BF%E8%BE%BC%E3%81%BF%E5%85%A5%E9%96%80%EF%BC%9Adirichlet%E7%A9%8D%E3%81%A8%E3%82%BC%E3%83%BC%E3%82%BF%E5%A4%89%E6%8F%9B%E3%83%BB%E3%83%A1%E3%83%93%E3%82%A6 // verify : https://atcoder.jp/contests/arc068/tasks/arc068_c s.resize(n + 1); s[0] = 0; repi(i, 1, n) s[i] = T(pow(i, k)); Divisor_transform<T> dt(n); dt.divisor_zeta(s); } // O(n log(log n)) mint TLE(ll n) { vm s; divisor_sigma(0, n, s); mint res = 0; repi(b, 1, n) { res += mint(n / b - 1) * (n - (n / b) + 1 - s[b]); } return res; } //【商列挙】O(√n) /* * i=[1..n] に対し,n/i の商が q となる i の範囲が [i1..i2) であることを * {q, i1, i2} として q について降順に qi に格納する. * 各範囲においては余りは公差 -q の等差数列を成す. */ void quotient_range(ll n, vector<tuple<ll, ll, ll>>& qi) { // verify : https://atcoder.jp/contests/abc230/tasks/abc230_e //【方法】 // n/i の商が q となるような i の範囲を考える.条件を i について整理すると // q = floor(n / i) // ⇔ q <= n / i < q + 1 // ⇔ i q <= n < i(q + 1) // ⇔ n / (q + 1) < i <= n / q // となる. // // この幅が 1 以下であれば,q に対応する i は高々 1 個である.その条件は // n / q - n / (q + 1) <= 1 // ⇔ (q + 1)n - q n <= q(q + 1) // ⇔ n <= q(q + 1) // である.条件をやや弱めて // n <= q^2 // ⇔ √n <= q // としてもオーダーに影響はない. //(例) // 例えば n = 15 のときは以下のように分類できる: // 商 n/i i の範囲 余り n%i // 15 [1..2) [0] // 7 [2..3) [1] // 5 [3..4) [0] // 3 [4..6) [3, 0] // 2 [6..8) [3, 1] // 1 [8..16) [7, 6, 5, 4, 3, 2, 1, 0] ll m = (ll)(sqrt(n) + EPS); // q に対応する i が高々 1 個の部分は i ごとに愚直に考える. for (int i = 1; n / i > m; i++) { qi.push_back({ n / i, i, i + 1 }); } // そうでない部分は q ごとにまとめて考える. repir(q, m, 1) { ll i0 = n / (q + 1LL) + 1; ll i1 = n / q + 1; qi.push_back({ q, i0, i1 }); } } void TLE2() { ll n0; cin >> n0; vector<tuple<ll, ll, ll>> qis; quotient_range(n0, qis); int m0 = (int)(sqrt(n0) + EPS); vm s_small; divisor_sigma(0, (int)1e6, s_small); // inv[i] : i の逆数 vm inv(msb(n0) + 10); repi(i, 1, sz(inv) - 1) inv[i] = mint(i).inv(); // 1 と素数の昇順リスト vl ps{ 1 }; // cnt0_p[v] : [2..v] 内の p 以下の素数で篩い終えた後残っている数の個数 // cnt1_p[v] : [2..n/v] 内の p 以下の素数で篩い終えた後残っている数の個数 vl cnt0(m0 + 1), cnt1(m0 + 1); repi(v, 1, m0) { cnt0[v] = v - 1; cnt1[v] = n0 / v - 1; } repi(p, 2, m0) { ll c = cnt0[p - 1]; // p が素数でなければ次の p へ if (cnt0[p] == c) continue; ps.push_back(p); // cnt1 の更新 repi(v, 1, m0) { // p^2 > n/v なら更新不要 if (p > n0 / v / p) break; if (v <= m0 / p) { cnt1[v] -= cnt1[v * p] - c; } else { cnt1[v] -= cnt0[n0 / v / p] - c; } } // cnt0 の更新 repir(v, m0, 1) { // p^2 > v なら更新不要 if (p > v / p) break; cnt0[v] -= cnt0[v / p] - c; } } mint res = 0; mint s1 = 0; repe(qi, qis) { ll q, i1, i2; tie(q, i1, i2) = qi; if (i2 - i1 == 1) { res += mint(q - 1) * (n0 - q + 1 - s_small[i1]); s1 += s_small[i1]; // dump(q, i1, i2, s1); continue; } ll n = i2 - 1; int m = (int)(sqrt(n) + EPS); mint s2 = 1; // s : 注目頂点, i_gpf : s の最大素因数が何番目の素数か, sg : σ_0(s), c : s の最大素因数の指数 function<void(ll, int, mint, int)> dfs = [&](ll s, int i_gpf, mint sg, int c) { // dump("dfs:", s, ps[i_gpf], sg, c); ll p = ps[i_gpf]; // s の最小の子 s * p からの寄与を加算する. if (s != 1) s2 += sg * inv[c + 1] * (c + 2); // その他の s の子からの寄与をまとめて加算する. if (n / s <= m0) s2 += sg * ((2 * cnt0[n / s]) - (2 * cnt0[p])); else s2 += sg * ((2 * cnt1[n0 / n * s]) - (2 * cnt0[p])); // s の最小の子 s * p を探索する. if (s != 1 && s <= n / (p * p)) dfs(s * p, i_gpf, sg * inv[c + 1] * (c + 2), c + 1); // その他の s の子を探索する. for (int i = i_gpf + 1; i < sz(ps) && s <= n / (ps[i] * ps[i]); i++) { dfs(s * ps[i], i, sg * 2, 1); } }; dfs(1, 0, 1, 0); res += mint(q - 1) * (mint(n0 - q + 1) * (i2 - i1) - (s2 - s1)); // dump(q, i1, i2, s1, s2); s1 = s2; } cout << res << endl; } void zikken2() { int N = 20; vm res(N + 1); repi(n, 1, N) { repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) { if (b % a == 0 && c % b == 0) res[n]++; } } dump_list(res); exit(0); } /* {0, 1, 4, 7, 13, 16, 25, 28, 38, 44, 53, 56, 74, 77, 86, 95, 110, 113, 131, 134, 152} http://oeis.org/A061201 To compute a(n) for huge n (see A180365) in sublinear use a(n) = 3*Sum_{i=1..n3} A006218(n/i) - Sum_{j=1..n3} floor(n/(i*j)) + n3^3, where n3 = floor(n^(1/3)). - Andrew Lelechenko, Apr 15 2011 http://oeis.org/A006218 a(n) = Sum_{k=1..n} floor(n/k); also Sum_{k=1..n} d(k), where d = number of divisors (A000005); also number of solutions to x*y = z with 1 <= x,y,z <= n. a(n) = 2*(Sum_{i=1..floor(sqrt(n))} floor(n/i)) - floor(sqrt(n))^2. - Benoit Cloitre, May 12 2002 */ //【長さ 2 の倍数鎖の数え上げ】O(√n) /* * 1 <= x | y <= n を満たす組 (x, y) の個数を返す. * * 利用:【商列挙】 */ template<class T> T count_multiple_2chain(ll n) { // 参考:http://oeis.org/A006218 //【方法】 // x を固定すれば,条件を満たす y は n 以下の x の倍数全てなので,その個数は floor(n/x) である. // よって求めるべき値は // Σx∈[1..n] floor(n/x) // である. // これは floor(n/x) の値が等しいところをまとめて計算することにより高速化できる. vector<tuple<ll, ll, ll>> qis; quotient_range(n, qis); T res = 0; repe(qi, qis) { ll q, i1, i2; tie(q, i1, i2) = qi; res += q * T(i2 - i1); } return res; } void check_count_multiple_2chain() { int N = 20; repi(n, 1, N) { ll res1 = 0; repi(a, 1, n) repi(b, 1, n) { if (b % a == 0) res1++; } ll res2 = count_multiple_2chain<ll>(n); dump(n, res1, res2); } exit(0); } /* 1 1 1 2 3 3 3 5 5 4 8 8 5 10 10 6 14 14 7 16 16 8 20 20 9 23 23 10 27 27 11 29 29 12 35 35 13 37 37 14 41 41 15 45 45 16 50 50 17 52 52 18 58 58 19 60 60 20 66 66 */ //【めぐる式二分探索】O(log|ok - ng|) /* * 条件 okQ() を満たす要素 ok と満たさない要素 ng との境界を二分探索する. * 境界に隣り合うような条件を満たす要素(ok 側)の位置を返す. */ template <typename T> T meguru_search(T ok, T ng, function<bool(T)>& okQ) { // 参考 : https://twitter.com/meguru_comp/status/697008509376835584 // verify : https://onlinejudge.u-aizu.ac.jp/courses/lesson/1/ALDS1/all/ALDS1_4_D // 境界が決定するまで while (abs(ok - ng) > 1) { // 区間の中間 T mid = (ok + ng) / 2; // 中間が OK かどうかに応じて区間を縮小する. if (okQ(mid)) ok = mid; else ng = mid; } return ok; /* okQ の定義の雛形 function<bool(ll)> okQ = [&](ll x) { return true || false; }; */ } //【整数累乗根】O(n log a) /* * 非負の数 a の n 乗根(a^(1/n))の切り捨て値を返す. * * 利用:【めぐる式二分探索】 */ ll integer_root(ll a, int n) { // verify : https://atcoder.jp/contests/abc166/tasks/abc166_d if (a <= 1 || n == 1) return a; // x^k を返す.ただし a を超えた場合は a + 1 を返す. auto pow = [&](ll x, int k) { ll v = 1; rep(i, k) { if (v > a / x) return a + 1; v *= x; } return v; }; // x^n <= a かを返す. function<bool(ll)> okQ = [&](ll x) { return pow(x, n) <= a; }; ll res = meguru_search(1LL, a + 1, okQ); return res; } //【長さ 3 の倍数鎖の数え上げ】O(n^(2/3)) ? /* * 1 <= x | y | z <= n を満たす組 (x, y, z) の個数を返す. * * 利用:【整数累乗根】,【長さ 2 の倍数鎖の数え上げ】 */ template<class T> T count_multiple_3chain(ll n) { // 参考:http://oeis.org/A061201 int m = (int)integer_root(n, 3); T res = T(m) * m * m; repi(i, 1, m) { res += 3 * count_multiple_2chain<T>(n / i); repi(j, 1, m) { res -= 3 * (n / ((ll)i * j)); } } return res; } void check_count_multiple_3chain() { int N = 20; repi(n, 1, N) { ll res1 = 0; repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) { if (b % a == 0 && c % b == 0) res1++; } ll res2 = count_multiple_3chain<ll>(n); dump(n, res1, res2); } exit(0); } /* 1 1 1 2 4 4 3 7 7 4 13 13 5 16 16 6 25 25 7 28 28 8 38 38 9 44 44 10 53 53 11 56 56 12 74 74 13 77 77 14 86 86 15 95 95 16 110 110 17 113 113 18 131 131 19 134 134 20 152 152 */ template<class T> T count_multiple_2Vchain(ll n) { vector<tuple<ll, ll, ll>> qis; quotient_range(n, qis); T res = 0; repe(qi, qis) { ll q, i1, i2; tie(q, i1, i2) = qi; res += T(q) * T(q) * T(i2 - i1); } return res; } void check_count_multiple_2Vchain() { int N = 20; repi(n, 1, N) { ll res1 = 0; repi(a, 1, n) repi(b, 1, n) repi(c, 1, n) { if (a % b == 0 && c % b == 0) res1++; } ll res2 = count_multiple_2Vchain<ll>(n); dump(n, res1, res2); } exit(0); } /* 1 1 1 2 5 5 3 11 11 4 22 22 5 32 32 6 52 52 7 66 66 8 92 92 9 115 115 10 147 147 11 169 169 12 219 219 13 245 245 14 289 289 15 333 333 16 390 390 17 424 424 18 496 496 19 534 534 20 612 612 */ int main() { // input_from_file("input.txt"); // output_to_file("output.txt"); ll n; cin >> n; mint c2 = count_multiple_2chain<mint>(n); mint c2V = count_multiple_2Vchain<mint>(n); mint c3 = count_multiple_3chain<mint>(n); mint cnt1111 = n; mint cnt1110 = c2 - cnt1111; mint cnt1011 = cnt1110; mint cnt0111 = cnt1110; mint cnt0011 = mint(n) * n - (cnt1111 + cnt1011 + cnt0111); mint cnt0110 = c2V - (cnt1111 + cnt0111+ cnt1110); mint cnt1010 = c3 - (cnt1111 + cnt1011 + cnt1110); mint cnt0010 = n * c2 - (cnt1111 + cnt1110 + cnt1011 + cnt0111 + cnt0011 + cnt0110 + cnt1010); cout << cnt0010 << endl; }