정보올림피아드 초등 - 지역예선] 2011년도 28번문제

 

 문제풀이)

m

5	0
2	1

 

num=1 인 경우

tmp

25	0
12	1

tmp[0][0] 은 m[0][0]의 제곱 + m[0][1] * m[1][0]의 값 = 25

tmp[0][1] 은 m[0][0] * m[0][1] + m[0][1] * m[1][1] 의 값 = 0

tmp[1][0] 은 m[1][0] * m[0][0] + m[1][1] * m[1][0] 의 값 = 12

tmp[1][1] 은 m[1][0] * m[0][1] + m[1][1] * m[1][1] 의 값 = 1

m

4	0
5	1

num =2 인 경우

tmp 

16	0
15	1

m

2	0
1	1

num = 3

m

4	0
5	1

여기서  num = 1 과 동일하다.

따라서 1,3,5,7,9,11 이 동일하다.

num = 11 인 경우

d = (4 * 1 - 0 * 5) % 7 = 4 이다

정답은 4