의외로 모르는 어떤 분수가 유한소수가 될 수 있는 조건

1. 유한소수?

 

유한소수는 소숫점 아래에 있는 수가 유한한 소수이다.

 

어떤 분수가 유한소수일려면 기약분수로 나타내고, 분모를 소인수분해 했을때, 2나 5만을 인수로 가져야한다.

 

왜냐하면, 유한소수는 (정수).xxxxxxx 형태로, 정수 + 0.xxxxxxx로 나타낼 수 있다.

 

이때, 0.xxxxxxxx = xxxxxxxxx/10^n이므로, (y + xxxxxxxxxx)/10^n형태로 나타난다.

 

따라서, 유한소수를 기약분수로 나타내 분모를 소인수분해해보면 반드시 2나 5만을 인수로 가진다.

 

 

2. 연습문제

 

https://atcoder.jp/contests/agc047/tasks/agc047_a

A - Integer Product

 

소수점 밑에 9자리까지 주어지는 실수 a1,a2,...,an가 주어질때, i < j에 대하여 ai*aj가 정수가 되는 (i,j) 쌍의 개수를 구한다

 

n <= 20만이라 단순하게 하면 무조건 시간초과

 

먼저 소수점 밑에 최대 9자리까지 주어진다고 하니까, 먼저 정수로 다루기 쉽게 10**9를 곱한 다음 정수로 바꿔준다.

 

여기서 중요한건

 

n = int(input())

for _ in range(n):
    
    a = float(input()) * (10**9)
    a = int(a)

 

 

이렇게 int(a)로 바꾸면 틀릴 수 있다는 것

 

 

 

그래서 int(a)가 아니고 round(a)로 해줘야함

 

n = int(input())

for _ in range(n):
    
    a = float(input()) * (10**9)
    a = round(a)

 

 

이제 10^9 * a의 분모에 2나 5가 몇개인지 확인한다.

 

a가 유한소수이기 때문에 반드시 분모는 2나 5만 존재한다는 점을 기억하라.

 

2로 나누어 떨어지지 않을때까지 2로 나눠보고, 나누어진 개수를 x개

 

5로 나누어 떨어지지 않을때까지 5로 나눠보고 나누어진 개수를 y개

 

(x,y)의 개수를 dp 테이블에 저장해둠

 

이거는 10^9*a가 2^x * 5^y * (나머지) 형태로 이루어짐을 말해주고 있다.

 

n = int(input())

dp = {}

for _ in range(n):
    
    a = float(input()) * (10**9)
    a = round(a)

    x,y = 0,0

    while a % 2 == 0:
        
        a //= 2
        x += 1
    
    while a % 5 == 0:
        
        a //= 5
        y += 1
    
    dp[(x,y)] = dp.get((x,y),0) + 1

 

 

이제 (x,y)와 (z,w)에 대하여, 두 수의 곱 (x+z,y+w)를 생각해보자.

 

10^9을 빼고 생각해보면, 

 

ai가 2^x*5^y*(나머지)

 

aj가 2^z*5^w*(나머지)

 

두 수의 곱으로 2^(x+z)*5^(y+w)*(나머지)인데, 이 x+z >= 0, y+w >=0이어야 2,5가 분모로 가지 않는다.

 

나머지는 반드시 분자에 있다. 왜냐하면 주어진 수가 유한소수이기 때문에 2,5를 제외한 수는 처음부터 분자에 있어야한다.

 

10^9이 곱해지면 적어도 9가 포함되어있으므로 그때 구한 (x',y'), (z',w')에 대하여

 

x' = (x+9)

y' = (y+9)

z' = (z+9)

w' = (w+9)

 

그러면 x+z >= 0, y+w >= 0이므로 x'-9 + z'-9 >= 0, y'-9 + w'-9 >= 0, 

 

x'+z' >= 18, y'+w' >= 18

 

n = int(input())

dp = {}

for _ in range(n):
    
    a = float(input()) * (10**9)
    a = round(a)

    x,y = 0,0

    while a % 2 == 0:
        
        a //= 2
        x += 1
    
    while a % 5 == 0:
        
        a //= 5
        y += 1
    
    dp[(x,y)] = dp.get((x,y),0) + 1

count = 0

for x,y in dp:
    
    for z,w in dp:
        
        if x+z >= 18 and y+w >= 18:
            
            if (x,y) < (z,w):
              
                count += (dp[(x,y)] * dp[(z,w)])
            
            elif (x,y) == (z,w):
                
                count += (dp[(x,y)] * (dp[(x,y)]-1))//2

print(count)

 

 

계산할때 주의해야한다.

 

for x,y in dp:

    

    for z,w in dp:

 

로 (x,y), (z,w)를 잡았으므로, 먼저 (x,y) = (z,w)인 경우에는

 

dp[(x,y)] 값이 대응하는 ai의 개수와 같으므로, 이 ai의 개수에서 서로 다른 2개를 선택하는 개수와 같게 된다.

 

즉 dp[(x,y)]C2 = dp[(x,y)]* (dp[(x,y)] - 1)//2

 

반대로 (x,y) != (z,w)인 경우에는?

 

dp[(x,y)]의 값에 대응하는 ai중 1개와 dp[(z,w)]의 값에 대응하는 aj중 1개를 선택하면 되므로, 두 수의 곱과 같다.

 

그런데 (x,y) != (z,w)인 경우에 다 하면 중복 계산된다.

 

그래서 (x,y) < (z,w)인 경우에만 두 수의 곱을 더해준다

 

i = 0,1,2,3,...에 대하여

 

j = 0,1,2,3,...으로 가는건데 

 

(i,j) 에 대하여 (0,0), (0,1), (0,2),...를 보고

 

(1,0), (1,1), (1,2),... 이렇게 보니까 (x,y) != (z,w)하면 (x,y) > (z,w)인 경우와 (x,y) < (z,w)인 경우 두 경우를 모두 보게 되잖아