반응형 정수론6 백준 6064번 카잉 달력 - 스위프트(Swift) 풀이 + 그림 설명 1. 에서 a를 x로 고정한다. → 2. a를 x로 고정하면 고려해야할 경우의 수는 N/GCD가지이다. 3. N/gcd가지 중에 b = y인 경우가 있는지 확인한다. 1. 에서 a를 x로 고정한다. → 1번째 해부터 마지막 해까지 모두 고려하면, M, N이 최대 40,000이므로 O(N^2)으로는 시간초과가 나게 된다. 둘 중에 하나를 고정해서 O(N)에 해결이 가능하도록 하자. 2. a를 x로 고정하면 고려해야할 경우의 수는 N/GCD가지이다. M = 3, N = 2인 경우를 생각해보자. 라고 하면 a자리는 1, 2, 3이 반복되고 b자리에는 1, 2가 반복된다. 따라서 M과 N의 최소공배수번째 해에 이 될 것이다. 총 LCM개의 해 중에서 a = x인 경우는 총 LCM / M가지가 될 것이다. 이때 .. 2022. 1. 21. 이전 1 2 다음 반응형