블로그 이사 중입니다 >> gumgood.github.io

6064 카잉 달력 본문

Problem Solving/문제 풀이

6064 카잉 달력

gumgood 2018. 11. 13. 13:33

C++11


x == M일 때, x = 0

y == N일 때, y = 0으로 생각하면,


연도 year 은 다음을 만족한다


year = x (mod M)

year = y (mod N)


year = iM + x = jN + y (i, j : nonnegative integer)


이 때, <x,y>가 표현할 수 있는 년도는 gcd(x,y)이므로 최대 x*y년도를 표현할 수 있다.


따라서 i와 j의 범위는 다음과 같다


0 <= i < N

0 <= j < M



모든 i에 대해 year(= iM + x)을 계산해서 year = y mod N 을 만족하는지 확인한다.


O(N)


 

'Problem Solving > 문제 풀이' 카테고리의 다른 글

1153 네 개의 소수  (0) 2019.01.15
3163 떨어지는 개미  (0) 2018.12.26
6064 카잉 달력  (0) 2018.11.13
2903 중앙 이동 알고리즘  (0) 2018.11.13
1351 무한 수열  (0) 2018.11.13
11066 파일 합치기  (0) 2018.11.13
0 Comments
댓글쓰기 폼