https://www.acmicpc.net/problem/1160Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net
이 문제 어떻게 푸는지 감도 안 잡히는데 고등학생 수준의 수학 지식으로는 못 풂??
행렬 필요한가
https://www.acmicpc.net/problem/1160Baekjoon Online JudgeBaekjoon Online Judgewww.acmicpc.net
이 문제 어떻게 푸는지 감도 안 잡히는데 고등학생 수준의 수학 지식으로는 못 풂??
행렬 필요한가
((a, c), (0, 1))
행렬 안 배워서 모름..
행렬 없이 설명하자면 a(ax + c) + c = (a^2)x + (ac +c)을 k번 반복하면 2^k번째 항목을 파바박 구할 수 있음
행렬 써서 설명하면 걍 ((a, c), (0, 1))^n ((x), (1)) 구하는 거
그냥 방정식으로 하는거 2^k가 아니라 그냥 2*k 아님? X=a0에서 시작해서 3번 반복한다고 a8이 구해지진 않고 a6이 구해지는 거 같은데.
f(x)가 ax+c일 때, g(x) = f(f(x))를 구한 다음 그 g를 다음 f로 씀. 단 여기서 말한 x는 문제에 주어진 x0를 쓴다는 게 아니라 함수의 인자를 뜻함. 또 다르게 말하면 a, c := a^2, ac + c를 k번 반복하겠다는 거임. 2^k 맞고 저렇게 구한 a c로 ax0 + c 하면 x8 나옴.
A = ((a, c), (0, 1))일 때 A^2 계산해 보면 똑같이 ((a^2, ac+c), (0, 1)) 나오는 것 볼 수 있고 이걸로 거듭제곱하는 거랑 같음. A^4 = (A^2)^2 (혹은 A^8 = (A^4)^2) 구하는 과정이랑 a, c := a^2, ac + c 두 세번 반복하는 거랑 비교해봐도 됨.
와 어렵네.. 일단 공부부터 하고 나중에 다시 풀어봐야겠다.. 고마워
플래정도에 나오는 선대정도는 금방 공부할수 있음 그냥 답지보면서 공부해도 충분한 정도임