UVa 275 Expanding Fractions

题目分析本题要求计算两个正整数的除法的小数展开形式其中分子小于分母分母小于100010001000。输入以0 0结束。对于每个分数需要输出其小数部分从小数点开始并且如果小数是有限的即能够整除则输出完整的小数部分。如果小数是无限的则输出到循环节第一次重复之前的数字并指出循环节长度。循环节必须是最短的。每行最多输出505050个字符包括小数点。每个测试用例的输出后跟一个空行。示例分析以输入3 7为例3/70.428571428571…3/7 0.428571428571\ldots3/70.428571428571…循环节为428571428571428571长度为666因此输出.428571 The last 6 digits repeat forever.以输入345 800为例345/8000.43125345/800 0.43125345/8000.43125是有限小数输出.43125 This expansion terminates.解题思路核心数学原理本题的核心是长除法模拟竖式除法和循环节检测。在长除法过程中每一步的余数决定了后续的小数位。根据抽屉原理鸽笼原理因为分母m1000m 1000m1000余数的取值范围是000到m−1m-1m−1共mmm种可能。因此如果某个余数重复出现则后续的小数序列将开始循环。如果余数变为000则除法终止小数是有限的。算法步骤初始化设置当前余数remainder n。记录余数出现的位置使用一个数组position记录每个余数第一次出现时的位数索引。标记余数是否出现过使用一个布尔数组appeared。模拟长除法每次将余数乘以101010然后除以分母得到当前小数位digit (remainder * 10) / m。更新余数remainder (remainder * 10) % m。如果remainder之前出现过则找到了循环节循环节从该余数第一次出现的位置开始到当前位置结束。如果remainder等于000则除法终止。输出先输出小数点.。每505050个字符换行注意小数点在行首也算一个字符。根据是否终止输出对应的提示信息。为什么这种方法能保证最短循环节由于我们从第一个小数位开始模拟并记录每个余数第一次出现的位置当余数重复时从该余数第一次出现的位置到当前位置之间的数字序列就是最小循环节。这是因为余数的重复直接决定了后续小数位的重复而第一次重复的余数位置对应着循环节的最早起点。复杂度分析时间复杂度O(m)O(m)O(m)因为最多模拟mmm步就会找到循环节或终止。空间复杂度O(m)O(m)O(m)用于存储余数出现的位置和标记数组。代码实现// Expanding Fractions// UVa ID: 275// Verdict: Accepted// Submission Date: 2016-05-11// UVa Run Time: 0.000s//// 版权所有C2016邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intn,m;vectorintdigits(1001);// 存储小数位的数字vectorintposition(1001);// 记录每个余数第一次出现的位置索引vectorboolappeared(1001);// 标记余数是否出现过intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);cout.sync_with_stdio(false);while(cinnm,nm){// 初始化标记数组fill(appeared.begin(),appeared.end(),false);intindex0;// 当前小数位的索引// 当余数未出现过且余数不为0时继续模拟while(!appeared[n]n0){appeared[n]true;// 标记当前余数已出现digits[index]10*n/m;// 计算当前小数位position[n]index;// 记录该余数出现的位置n10*n%m;// 更新余数}// 输出小数点cout.;// 输出所有已计算的小数位for(inti0;iindex;i){// 每50个字符换行包括前面的小数点但这里i从0开始if(i%5049)cout\n;coutdigits[i];}// 判断是有限小数还是无限循环小数if(n0)// 余数为0说明除法终止cout\nThis expansion terminates.\n\n;else// 循环节的长度 当前索引 - 循环节开始的位置cout\nThe last (index-position[n]);cout digits repeat forever.\n\n;}}return0;}总结本题的关键在于理解长除法过程中余数与循环节的关系。通过模拟除法并记录余数出现的位置可以高效地找到最短循环节。由于分母的最大值为999999999算法的复杂度非常低可以轻松通过。