问题描述
p202原题链接：UVaOJ 202 - Repeating Decimals
相关说明：本题为《算法竞赛入门经典（第2版）》习题 3-8
解法一：模拟（数论）
这题虽然输入输出是字符串，但本质上是一个模拟除法过程，求循环节长度的数论题。
核心结论是：如果在模拟除法计算的过程中，出现了相同的余数（Remainder），则表明商（Quotient）的循环节完成了。
|
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 |
#include <bits/stdc++.h> using namespace std; int main() { const int MAX_LEN = 50; int numerator, denominator; while (cin >> numerator >> denominator) { cout << numerator << "/" << denominator << " = "; vector<int> index(denominator, -1), quotient; quotient.push_back(numerator / denominator); int remainder = numerator % denominator, pos = 0; while (remainder && index[remainder] == -1) { index[remainder] = pos++; quotient.push_back(remainder * 10 / denominator); remainder = remainder * 10 % denominator; } int cur_index = 0; cout << quotient[cur_index++] << "."; if (remainder) { while (cur_index <= pos && cur_index <= MAX_LEN) { if (cur_index == index[remainder] + 1) cout << "("; cout << quotient[cur_index++]; } cout << (pos < MAX_LEN ? ")\n" : "...)\n"); } else { while (cur_index <= pos) cout << quotient[cur_index++]; cout << "(0)\n"; } cout << " " << (remainder ? pos - index[remainder] : 1) << " = number of digits in repeating cycle\n\n"; } 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 |
MAX_LEN = 50 while True: try: numerator, denominator = map(int, input().split()) print("{numerator}/{denominator}", end="") index = [-1 for _ in range(denominator)] quotient = [numerator // denominator] remainder = numerator % denominator pos = 0 while remainder and index[remainder] == -1: index[remainder] = pos quotient.append(remainder * 10 // denominator) remainder = remainder * 10 % denominator pos += 1 cur_index = 0 print("{quotient[cur_index]}.", end="") cur_index += 1 if remainder: while cur_index <= pos and cur_index <= MAX_LEN: if cur_index == index[remainder] + 1: print("(", end="") print("{quotient[cur_index]}.", end="") cur_index += 1 print(")" if pos < MAX_LEN else "...)") else: while cur_index <= pos: print("{quotient[cur_index]}.", end="") cur_index += 1 print("(0)") res = pos - index[remainder] if remainder else 1 print(" {res} = number of digits in repeating cycle\n") except EOFError: break |
