Fraction to Recurring Decimal

首先这道题有个相对简单的版本即求1/n的分数的循环节，如果没有循环节则用0表示，实际上不管是原题还是这个简单版本，他们的核心都是利用哈希表记录出现过的余数，因为所有的分数都是有理数，所以它们必定都是整除小数或者无限循环小数，也就是说循环节不可能超过10位数，而当重复余数出现时就说明循环节已经完全出现了，可以不用继续进行除法循环了

def gen(n):
    rem = 1
    result = ''
    checker = {}
    while rem:
        if rem in checker:
            return result[checker[rem]:]
        else:
            checker[rem] = len(result)
            rem *= 10
            result += str(rem / n)
            rem %= n

    return '0'

此外这里的rem是可以换成任何分子上述代码都能成立的，唯一的区别在于负数分子时我们需要先把分子转成正数，另外这里输出的答案是循环节数而不是整个除法的结果本身，这点也是LC原题的另外一个难点了