結果

問題 No.1842 Decimal Point
コンテスト
ユーザー Gaotian0109
提出日時 2025-10-15 18:33:26
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
TLE  
実行時間 -
コード長 3,491 bytes
コンパイル時間 891 ms
コンパイル使用メモリ 83,352 KB
実行使用メモリ 180,572 KB
最終ジャッジ日時 2025-10-15 18:33:37
合計ジャッジ時間 10,481 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other WA * 1 TLE * 2 -- * 2
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <iostream>
#include <unordered_map>
using namespace std;

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    
    int T;
    cin >> T;
    while (T--) {
        long long A, B, C;
        cin >> A >> B >> C;
        
        // 处理整除情况：小数部分全为0
        if (A % B == 0) {
            cout << "0\n";
            continue;
        }
        
        // 提取余数（小数部分由余数决定）
        long long rem = A % B;
        
        // 消除B中所有2和5的因子，计算非循环前缀长度
        int a = 0, b = 0;
        long long temp_B = B;
        while (temp_B % 2 == 0) {
            temp_B /= 2;
            a++;
        }
        while (temp_B % 5 == 0) {
            temp_B /= 5;
            b++;
        }
        int prefix_len = max(a, b);
        
        // 情况1：C在非循环前缀范围内
        if (C <= prefix_len) {
            long long current_rem = rem;
            for (int i = 0; i < C; ++i) {
                current_rem *= 10;
                if (i == C - 1) {
                    cout << current_rem / B << '\n';
                    break;
                }
                current_rem %= B;
                // 若余数变为0，后续全为0
                if (current_rem == 0) {
                    cout << "0\n";
                    break;
                }
            }
            continue;
        }
        
        // 情况2：C在循环部分（需处理大C值）
        // 1. 先将余数推进到循环部分起点
        long long current_rem = rem;
        for (int i = 0; i < prefix_len; ++i) {
            current_rem = (current_rem * 10) % B;
        }
        
        // 2. 寻找循环节
        unordered_map<long long, int> rem_pos; // 记录余数首次出现的位置
        int pos = 0; // 当前是循环部分的第几位（从0开始）
        long long target_rem = current_rem;
        int cycle_start = -1, cycle_len = -1;
        
        while (true) {
            if (rem_pos.count(target_rem)) {
                cycle_start = rem_pos[target_rem];
                cycle_len = pos - cycle_start;
                break;
            }
            rem_pos[target_rem] = pos;
            target_rem = (target_rem * 10) % temp_B; // 用消去因子后的B计算更高效
            pos++;
        }
        
        // 3. 计算C在循环部分的位置
        long long cycle_pos = C - prefix_len - 1; // 循环部分从0开始计数
        if (cycle_pos < cycle_start) {
            // 还没进入循环节，直接计算
            target_rem = current_rem;
            for (int i = 0; i <= cycle_pos; ++i) {
                if (i == cycle_pos) {
                    cout << (target_rem * 10) / temp_B << '\n';
                    break;
                }
                target_rem = (target_rem * 10) % temp_B;
            }
        } else {
            // 已进入循环节，计算循环偏移
            long long offset = (cycle_pos - cycle_start) % cycle_len;
            long long final_pos = cycle_start + offset;
            
            // 找到循环节中对应位置的数字
            target_rem = current_rem;
            for (int i = 0; i <= final_pos; ++i) {
                if (i == final_pos) {
                    cout << (target_rem * 10) / temp_B << '\n';
                    break;
                }
                target_rem = (target_rem * 10) % temp_B;
            }
        }
    }
    
    return 0;
}
0