結果

問題 No.1842 Decimal Point
ユーザー vjudge1
提出日時 2025-08-04 17:19:15
言語 C++23
(gcc 13.3.0 + boost 1.87.0)
結果
WA  
実行時間 -
コード長 2,803 bytes
コンパイル時間 3,121 ms
コンパイル使用メモリ 278,520 KB
実行使用メモリ 7,716 KB
最終ジャッジ日時 2025-08-04 17:19:19
合計ジャッジ時間 4,240 ms
ジャッジサーバーID
（参考情報） 		judge3 / judge1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 1 WA * 2 RE * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#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;
        __int128_t base = a;
        while (b) {
            if (b & 1) {
                res = (res * base) % mod;
            }
            base = (base * base) % mod;
            b >>= 1;
        }
        return (ll)res;
    }
    ll get(ll p, ll q, ll k) {
        ll r = p % q;
        if (r < 0) r += q;
        ll mod = q * 10;
        ll x = pw(10, k, mod);
        x = (x * r) % mod;
        if (x < 0) x += mod;
        return x / q;
    }
    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;
}
0