当前位置：首页 > news >正文

UVa 275 Expanding Fractions

news 2026/5/23 12:38:49

题目分析

本题要求计算两个正整数的除法的小数展开形式，其中分子小于分母，分母小于100010001000。输入以0 0结束。

对于每个分数，需要输出其小数部分（从小数点开始），并且：

如果小数是有限的（即能够整除），则输出完整的小数部分。
如果小数是无限的，则输出到循环节第一次重复之前的数字，并指出循环节长度。
循环节必须是最短的。
每行最多输出505050个字符（包括小数点）。
每个测试用例的输出后跟一个空行。

示例分析

以输入3 7为例，3/7=0.428571428571…3/7 = 0.428571428571\ldots3/7=0.428571428571…，循环节为428571428571428571，长度为666，因此输出：

.428571 The last 6 digits repeat forever.

以输入345 800为例，345/800=0.43125345/800 = 0.43125345/800=0.43125，是有限小数，输出：

.43125 This expansion terminates.

解题思路

核心数学原理

本题的核心是长除法（模拟竖式除法）和循环节检测。

在长除法过程中，每一步的余数决定了后续的小数位。根据抽屉原理（鸽笼原理），因为分母m<1000m < 1000m<1000，余数的取值范围是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//// 版权所有（C）2016，邱秋。metaphysis # yeah dot net#include<bits/stdc++.h>usingnamespacestd;intn,m;vector<int>digits(1001);// 存储小数位的数字vector<int>position(1001);// 记录每个余数第一次出现的位置索引vector<bool>appeared(1001);// 标记余数是否出现过intmain(intargc,char*argv[]){cin.tie(0);cout.tie(0);cout.sync_with_stdio(false);while(cin>>n>>m,n&&m){// 初始化标记数组fill(appeared.begin(),appeared.end(),false);intindex=0;// 当前小数位的索引// 当余数未出现过且余数不为0时继续模拟while(!appeared[n]&&n>0){appeared[n]=true;// 标记当前余数已出现digits[index]=10*n/m;// 计算当前小数位position[n]=index++;// 记录该余数出现的位置n=10*n%m;// 更新余数}// 输出小数点cout<<".";// 输出所有已计算的小数位for(inti=0;i<index;i++){// 每50个字符换行（包括前面的小数点，但这里i从0开始）if(i%50==49)cout<<"\n";cout<<digits[i];}// 判断是有限小数还是无限循环小数if(n==0)// 余数为0，说明除法终止cout<<"\nThis expansion terminates.\n\n";else// 循环节的长度 = 当前索引 - 循环节开始的位置cout<<"\nThe last "<<(index-position[n]);cout<<" digits repeat forever.\n\n";}}return0;}