結果
問題 |
No.1842 Decimal Point
|
ユーザー |
![]() |
提出日時 | 2025-08-04 17:17:15 |
言語 | C++23 (gcc 13.3.0 + boost 1.87.0) |
結果 |
WA
|
実行時間 | - |
コード長 | 2,746 bytes |
コンパイル時間 | 3,769 ms |
コンパイル使用メモリ | 278,388 KB |
実行使用メモリ | 7,716 KB |
最終ジャッジ日時 | 2025-08-04 17:17:20 |
合計ジャッジ時間 | 4,503 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 1 WA * 2 RE * 2 |
ソースコード
#include <bits/stdc++.h> using namespace std; using ll = long long; int tc; ll p[1003], q[1003], s[1003], t[1003], mp, mq, ms, mt; namespace sub1 { bool check() { return (mp <= 100 && mq <= 100 && ms <= 1e18 && mt <= 1e18); } int pf[1003], cyc[1003], vis[1003]; ll p1[1003], p2[1003]; int szp, szl; void build(int p, int q) { fill(vis, vis + 1003, -1); fill(pf, pf + 1003, 0); fill(cyc, cyc + 1003, 0); fill(p1, p1 + 1003, 0); fill(p2, p2 + 1003, 0); szp = szl = 0; int r = p % q; int id = 0; while (r && vis[r] == -1) { vis[r] = ++id; r *= 10; int dg = r / q; r %= q; pf[id] = dg; } if (r == 0) { szp = id; szl = 0; } else { int st = vis[r]; szp = st - 1; szl = id - st + 1; for (int i = 1; i <= szl; i++) { cyc[i] = pf[st + i - 1]; } } for (int i = 1; i <= szp; i++) { p1[i] = p1[i - 1] + pf[i]; } for (int i = 1; i <= szl; i++) { p2[i] = p2[i - 1] + cyc[i]; } } ll get(ll n) { if (n <= 0) return 0; if (n <= szp) return p1[n]; ll ans = p1[szp]; if (szl == 0) return ans; ll r = n - szp; ll c1 = r / szl; ll r1 = r % szl; ans += c1 * p2[szl]; ans += p2[r1]; return ans; } void calc() { for (int i = 1; i <= tc; i++) { build(p[i], q[i]); cout << get(t[i]) - get(s[i] - 1) << "\n"; } } } namespace sub2 { bool check() { return (mp <= 1e9 && mq <= 1e9 && ms <= 1e9); } ll pw(ll a, ll b, ll mod) { a %= mod; __int128_t res = 1; while (b) { if (b & 1) { res = (res * a) % mod; } a = (ll)((__int128_t)a * a % mod); b >>= 1; } return (ll)res; } int get(ll p, ll q, ll k) { ll m = q * 10; ll x = pw(10, k, m); ll r = p % q; ll t = ((__int128_t)r * x) % (m); t /= q; return t; } void calc() { for (int i = 1; i <= tc; i++) { cout << get(p[i], q[i], s[i]) << "\n"; } } } int main() { ios_base::sync_with_stdio(false); cin.tie(NULL); cout.tie(NULL); cin >> tc; for (int i = 1; i <= tc; i++) { cin >> p[i] >> q[i] >> s[i]; mp = max(mp, p[i]); mq = max(mq, q[i]); ms = max(ms, s[i]); mt = max(mt, t[i]); } //if (sub1::check()) sub1::calc(); if (sub2::check()) sub2::calc(); return 0; }