有理数的循环节

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

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

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

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

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

输入输出样例
示例
输入

1,7

输出

0.[142857]

思路

• 先模拟手算，找规律，这里不妨用题目所给的例子： 1 ÷ 7 1 \div 7 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;
}