企业官网建设流程全解析

题目描述

给定两个正整数，分别表示一个分数的分子与分母，要求输出该分数对应小数的循环节表示形式。循环表示的形式为d1…di.dj…dl(dm…dn)d_1\ldots d_i.d_j\ldots d_l(d_m\ldots d_n)d1​…di​.dj​…dl​(dm​…dn​)，其中括号内的数字序列表示无限重复的循环节。若小数部分有限，则省略括号部分，仅输出有限小数。所有分数都可以用这种形式精确表示，但循环节的长度没有显式上界。

输入格式

第一行包含一个非负整数nnn，表示需要转换的分数个数。接下来nnn行，每行包含两个正整数，分别表示分数的分子和分母。

输出格式

对于输入的每个分数，输出一行，表示其小数的循环表示形式。

样例输入

7 4 33 912 89 120 3 131 909 146 325 12345 88 18 12000

样例输出

0.(12) 10.(24719101123595505617977528089887640449438202) 40.0 0.(1441) 0.44(923076) 140.284(09) 0.0015

题目分析

本题要求将分数转换为小数并识别其循环节。核心难点在于判断小数部分从哪一位开始进入循环，以及循环节的具体内容。由于分母可能很大，直接进行高精度除法并检测循环是不可行的，需要利用余数出现的位置来确定循环的起点与长度。

分数n/mn / mn/m的小数部分可以通过长除法生成。在每一步中，将当前余数乘以101010后再除以mmm，得到的商即为当前位的小数数字，新的余数用于下一步。若某个余数在之前已经出现过，则说明从该余数首次出现的位置开始，后续的数字序列将开始循环。因此，记录每个余数首次出现的位置，即可确定循环节的起点和长度。

需要注意整数部分的处理：先输出n/mn / mn/m的整数部分，再将nnn对mmm取模。若余数为000，说明小数部分有限，直接输出0即可。对于循环节部分，若存在循环，则在循环节前输出(，循环节后输出)；若小数部分有限，则不输出括号。

解题思路

首先计算整数部分并输出，同时将分子对分母取模。若余数为000，说明该分数为整数，直接输出0并换行。

若余数不为000，则进入长除法过程。使用一个哈希表记录每个余数首次出现的位置，同时用一个数组保存每一步产生的商（即小数位）。在每一步中，检查当前余数是否已经出现过：若出现过，则说明从该余数首次出现的位置开始进入循环，记录循环起点loop；若未出现过，则记录当前余数对应的位置，然后执行n←n×10n \leftarrow n \times 10n←n×10，将n/mn / mn/m加入商数组，并更新n←n mod mn \leftarrow n \bmod mn←nmodm。

当循环结束时，若存在循环节（即loop被设置），则先输出循环起点之前的非循环部分，再输出(和循环节，最后输出)；若不存在循环节，则直接输出整个商数组。注意输出格式中的小数点位置和换行处理。

代码实现

// Cyclic Numbers// UVa ID: 942// Verdict: Accepted// Submission Date: 2017-03-16// UVa Run Time: 0.020s//// 版权所有（C）2017，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,n,m;cin>>cases;for(intc=1;c<=cases;c++){cin>>n>>m;cout<<(n/m)<<'.';n%=m;if(n==0){cout<<"0\n";continue;}unordered_map<int,int>appeared;vector<int>quotient;while(n>0){if(appeared.find(n)!=appeared.end())break;appeared[n]=quotient.size();n*=10;quotient.push_back(n/m);n%=m;}intloop=0;if(n>0){loop=appeared[n];for(inti=0;i<loop;i++)cout<<quotient[i];cout<<'(';}for(inti=loop;i<quotient.size();i++)cout<<quotient[i];if(n>0)cout<<')';cout<<'\n';}return0;}

总结

本题的关键在于利用余数出现的位置来判断循环节的起点和长度。通过哈希表记录每个余数首次出现的位置，可以高效地识别循环。需要注意整数部分的处理、有限小数的特殊情况以及输出格式的细节。时间复杂度为O(m)O(m)O(m)，其中mmm为分母，空间复杂度为O(m)O(m)O(m)，能够满足题目要求。