题目难度:二星
考察点:模拟

方法:模拟

1.分析:

这个题的结果一共有如下三种情况:
(1). a%b==0,在这种情况下直接输出a/b即可。
(2). a/b为有限不循环小数,即a/b一定有一个可以得到的真实值,显然整数部分是很好得到的,即int(a/b),那么我们如何来输出小数部分呢?其实我们可以按照列竖式的方法一步步模拟,我们想计算a/b的小数部分,首先得到了余数部分t=a%b,然后余数乘以10,在对b求商,然后在得到余数,在对b求商,一步步继续下去,直到满足一个条件就是t%b==0,其中t就是每次得到的余数。那么此时我们就已经计算出所有的小数部分了,直接跟之前的整数部分连接,输出 即可。
(3). a/b为无限循环小数,对于此种情况,我们还是跟第二种的算法差不多,也是求余数,然后对b求商,但是在计算的过程中可以用一个map来标记一下所得到的余数,如果余数出现了两次,那么说明就一定是有限循环小数,然后我们加上括号输出即可,至于在哪加括号,我们用map标记的时候顺便把下标标记了一下,所以假设k是第二次出现的余数,那么就在map[k]处加括号输出就好了。
当然还有一种情况是无限不循环小数,但是如果是这样的话,题就没法做了,所以暂时不考虑这种情况。

算法实现:
(1). 输入一个两个整数a,b。
(2). 输出int(a/b),然后判断a%b是否为0,如果为0,那么直接结束,否则继续循环while(t) 其中t就是每次计算得到的余数
(3). 按照之前的做法,将t*10%b得到的商放在结果中,然后判断是否有余数出现了两次,如果出现两次,那么循环结束,证明是有限循环小数
(4). 根据是不是有限循环小数进行输出答案,其中答案就是记录的商,具体可以详见代码。

2.复杂度分析:

时间复杂度:O(n) 其中n为小数部分的长度。
空间复杂度:O(1)

3.代码:

#include <bits/stdc++.h>
using namespace std;
typedef long long LL;
int main() {
    int a, b; cin>>a>>b;
    cout<<a/b;
    int t = a % b;
    if(t == 0) return 0;
    cout<<".";
    map<int, int> mp;
    vector<int> ans;
    int cnt = 0;
    while(t) {
        if(mp.count(t)) break;
        mp[t] = cnt++;
        t *= 10;
        ans.push_back(t/b);
        t %= b;
    }
    if(t == 0) {
        for(int i=0; i<ans.size(); i++) cout<<ans[i];
    }
    else {
        for(int i=0; i<mp[t]; i++) cout<<ans[i];
        cout<<"(";
        for(int i=mp[t]; i<ans.size(); i++) cout<<ans[i];
        cout<<")";
    }
    return 0;
}