题目描述给定两个正整数分别表示一个分数的分子与分母要求输出该分数对应小数的循环节表示形式。循环表示的形式为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//// 版权所有C2017邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);ios::sync_with_stdio(false);intcases,n,m;cincases;for(intc1;ccases;c){cinnm;cout(n/m).;n%m;if(n0){cout0\n;continue;}unordered_mapint,intappeared;vectorintquotient;while(n0){if(appeared.find(n)!appeared.end())break;appeared[n]quotient.size();n*10;quotient.push_back(n/m);n%m;}intloop0;if(n0){loopappeared[n];for(inti0;iloop;i)coutquotient[i];cout(;}for(intiloop;iquotient.size();i)coutquotient[i];if(n0)cout);cout\n;}return0;}总结本题的关键在于利用余数出现的位置来判断循环节的起点和长度。通过哈希表记录每个余数首次出现的位置可以高效地识别循环。需要注意整数部分的处理、有限小数的特殊情况以及输出格式的细节。时间复杂度为O(m)O(m)O(m)其中mmm为分母空间复杂度为O(m)O(m)O(m)能够满足题目要求。