백준 24551번 일이 너무 많아... - 파이썬(Python) 풀이

---

 

1. N 이하인 자연수들 중 X의 배수인 수의 개수는 N / X개이다.
2. 포함배제의 원리를 이용하여 2개 이상의 1들로만 이루어진 수의 배수인 수들의 개수를 구한다.
2. A의 배수들로 이루어진 집합과 B의 배수들로 이루어진 집합의 교집합은 A와 B의 최소공배수들로 이루어진 집합이다.

 

1. N 이하인 자연수들 중 X의 배수인 수의 개수는 N / X개이다.

 2개 이상의 숫자 1로만 이루어진 숫자를 약수로 가지는 수는 2개 이상의 숫자 1로만 이루어진 숫자의 배수이다. N 이하인 자연수들 중 X의 배수인 수의 개수는 N / X개이다.

 

 

2. 포함배제의 원리를 이용하여 2개 이상의 1들로만 이루어진 수의 배수인 수들의 개수를 구한다.

 F(X)을 X의 배수이면서 N 이하인 자연수들의 집합이라고 하면, 구해야하는 것은 F(11) ∪ F(111) ∪ F(1111) ∪ ... ∪ F(111111111111111111) 의 크기이다. 따라서 포함배제의 원리에 따라 교집합의 크기를 구해 더하거나 빼주면 된다. 그런데 1로만 이루어진 수 A와 B가 있을 때, A의 길이가 B의 길이의 배수이면 A는 B의 배수(ex. 1111은 11의 배수)이기 때문에 길이가 소수인 수(11, 111, 11111, 1111111, ...)만 고려해주어도 된다.

 

3. A의 배수들로 이루어진 집합과 B의 배수들로 이루어진 집합의 교집합은 A와 B의 최소공배수들로 이루어진 집합이다.

 A의 배수들의 집합과 B의 배수들의 집합의 교집합은 A와 B의 최소공배수의 배수들의 집합이다. 교집합의 크기를 구할 때는 이것을 이용하면 된다. 최소공배수는 A * B / gcd(A, B)로 구할 수 있는데, N의 크기가 크기 때문에 A * B 과정에서 오버플로우가 발생할 수 있어 큰 수 연산을 지원하는 Python을 사용해서 풀이하였다.

 

반응형

---

def GCD(a, b):
  if b == 0:
    return a
  else:
    return GCD(b, a%b)

def LCM(a, b):
  return a * b // GCD(a, b)

def count_one(mask):
    cnt = 0
    
    for i in range(0, 7):
        if mask & (1 << i) != 0:
            cnt += 1
    
    return cnt

def LCMs(mask):
    ret = 1;
    
    for i in range(0, 7):
        if mask & (1 << i) != 0:
            ret = LCM(ret, arr[i])
    
    return ret

N = int(input())
arr = [11, 111, 11111, 1111111, 11111111111, 1111111111111, 11111111111111111]

ret = N;

for i in range(0, (1 << 7)):
    if count_one(i) % 2 == 0:
        ret -= N // LCMs(i)
    else:
        ret += N // LCMs(i)
            
print(ret)