난이도

Gold 5

인증

문제

모든 유리수는 다음과 같이 특정한 수가 반복되는 순환 소수 형태로 표현될 수 있다.

[\frac{1}{3} = \frac{3}{9} = 0.3333333\dots = 0.\overline{3} \ \frac{1}{7} = \frac{142857}{999999} = 0.14285714285714\dots = 0.\overline {142857} \ \frac{3}{14} = \frac{2142855}{9999990} = 0.214285714285714 = 0.2\overline{142857}] 

위에서 분모가 9와 0으로 이루어진 부분을 보면 알 수 있듯이 순환 소수가 주어졌을 때 이를 분수로 바꾸는 방법은 공식화 되어있다. 하지만 공식의 형태가 아닌 분수가 주어졌을 때 이를 이용하기는 어려우므로 일반적으로 분수를 순환 소수로 바꾸는 가장 쉬운 방법은 나눗셈을 반복하는 것이다. 하지만 이 작업은 손으로 하기엔 너무 어려우니 이를 수행하는 프로그램을 작성해보자.

입력

입력의 첫 번째 줄에는 테스트 케이스의 수 T (1 ≤ T ≤ 15,000)가 주어진다.

이후 각 테스트 케이스에 대해 한 줄에 분자와 분모 (0 ≤ 분자 < 1024, 0 < 분모 < 1024)가 공백으로 구분되어 정수로 주어진다

출력

한 줄에 한 개씩 각 테스트 케이스에 대한 순환소수를 출력한다(순환부는 괄호로 감싸서 표시한다).

예제 입력

6
1 2
1 7
10 5
11 5
995 476
991 994

예제 출력

0.5(0)
0.(142857)
2.(0)
2.2(0)
2.09(033613445378151260504201680672268907563025210084)
0.9(969818913480885311871227364185110663983903420523138832997987927565392354124748490945674044265593561368209255533199195171026156941649899396378269617706237424547283702213279678068410462776659959758551307847082494)

해설 및 후기

얕잡아 봤다가 상당히 오래 걸렸다. ‘졸려’문제와 비슷하게 순환되는 경우를 찾아야 하는데, 나머지가 같은 경우를 기준으로 순환소수를 판별했다.

제출 코드

n = int(input())
for i in range(n):
    a, b = map(int, input().split())
    nums = []
    f = a//b
    isVis = [-1 for _ in range(b)]
    toMod = a%b
    last = 0
    has = False
    t = 0
    isVis[toMod] = t
    t+=1

    while(toMod != 0):
        toMod *= 10
        d = toMod // b
        m = toMod % b

        nums.append(d)

        if(isVis[m] != -1):
            has = True
            last = isVis[m]
            break
            
        isVis[m] = t
        t += 1
        toMod = m


    print(f,end=".")
    if(has):
        for j in range(last):
            print(nums[j],end="")
        print("(",end="")
        for j in range(last, len(nums)):
            print(nums[j],end="")
        print(")")
    else:
        for j in nums:
            print(j,end="")
        print("(0)")