有理数的循环节

$1/7=0.142857142\cdots \cdots$ 是个无限循环小数。

任何有理数都可以表示为无限循环小数的形式。

题目要求即是：给出一个数字的循环小数表示法。

输入描述
输入一行，两个整数。
每个整数范围均为：1 ~ 1000。

输出描述
输出两个整数做除法产生的小数或无限循环小数（循环节用方括号括起）。

输入输出样例
示例
输入

1,7

输出

0.[142857]

思路

• 先模拟手算，找规律，这里不妨用题目所给的例子：$1÷7$
  • 1除以7，商0余1，点上小数点，余数不为0，则把余数1乘以10之后继续除以7(即“添0继续除”)
  • 10除以7，商1余3，余数不为0，添0继续除
  • 30除以7，商4余2，余数不为0，添0继续除
  • 20除以7，商2余6，余数不为0，添0继续除
  • 60除以7，商8余4，余数不为0，添0继续除
  • 40除以7，商5余5，余数不为0，添0继续除
  • 50除以7，商7余1，余数不为0，添0继续除
  • $\cdots \cdots$

到这里，可能已经看出规律了，再继续除下去的话就循环起来了，则已经找出了循环节

• 然后发现，循环节的最后一个数出现的时候，其对应的余数恰好是出现过的，而这个余数上一次出现时乘10除以除数得到的商恰好是循环节的第一个数
• 这样问题就差不多解决了，因为已经确定了循环节的首尾位置
• 由于题目还要求输出中括号，所以商用一个数组来存放比较方便
• 怎么知道余数已经出现过了？怎么确定循环节的第一个数字？
• 综合考虑，选用哈希表记录出现过的余数，并且将余数和小数点后的位号(数组下标)建立联系，方便确定循环节
• 通过模拟，应该还能得出一个显然的规律：当相除的结果是无限循环小数时，最后一个数字一定是循环节的最后一个数字，且最终答案的最后一个字符一定是 $]$；而除得尽的话，就直接输出结果就行，但是依然要用数组来存放，因为好判断是否能除尽
• 将商的整数部分和小数部分分开比较好

代码如下

#include <iostream>
#include <unordered_map>
#include <vector>
using namespace std;unordered_map<int, int> mp;  //余数<->下标
vector<int> data;            //存放小数部分的数组
int n, m;                    //分子，分母void solve() {int res = 0;  //整数部分商int t = 0;    //下标scanf("%d,%d", &n, &m);//坑点，要把逗号加进去//处理整数部分res = n / m;n %= m;mp[n] = t++;//处理小数部分while (true) {if (n == 0) {//这是除得尽的情况printf("%d.", res);//整数部分//小数部分全部输出for (int i = 0; i < int(data.size()); i++) {printf("%d", data.at(i));}printf("\n");break;}n *= 10;//添0继续除data.push_back(n / m);//商n %= m;//余数更新被除数//余数不为0且余数出现过if (n && mp.find(n) != mp.end()) {printf("%d.", res);//输出整数部分//输出循环节之前的小数部分，有些循环小数要等几个数之后才开始循环for (int i = 0; i < mp[n]; i++) {printf("%d", data.at(i));}//输出循环节printf("[");for (int i = mp[n]; i < (int)data.size(); i++) {printf("%d", data.at(i));}printf("]\n");break;} else {//否则加入mp[n] = t++;}}
}int main(void) {solve();return 0;
}