ghkd3778   4년 전

난수라고 해도 n % (m-1)번마다 반복되는 것 같길래 그 수까지 for 반복해줬는데 시간 초과가 뜹니다..
이 문제 푸신 분, 팁을 주실 수 있으실까요.

atomzeno   4년 전

직접 순차대로 계산하지 말고 지수승을 빠르계 계산하는 방법을 생각해 보세요 ㅎㅎ

atomzeno   4년 전

a^n을 구하고 싶으면

a^1,a^2,a^4,a^8,...,a^(2^64) 계산하고(mod 연산은 알아서)

n을 이진법으로 바꾸어서 n=5이면, 101(2) 이니까,

(a^4)*(a^1) 만 계산해주시면, logn만에 구할 수 있습니다.

Xn=a^n*(X0)+c*(1+a+...+a^(n-1))인데,

이것도 비슷하게 n=13이면 (1+a+...+a^7)*(a^6)+(1+a+...+a^3)*(a^2)+(a^1)*(a^0) 로 계산가능

(1+a+...+a^(2^n))=(1+a^(2^(n-1)))*(1+a+...+a^(2^(n-1)))로 귀납적으로 계산 가능

이렇게 열심히?? 계산하시면 될듯

ghkd3778   4년 전

감사합니다!!!

댓글을 작성하려면 로그인해야 합니다.