r을 (a-1)n+(a+1)n을 a2으로 나누었을 때 나머지로 하자.
예를 들어, a=7이고 n=3일 때, r=42가 된다(63+83=728≡42 mod 49). 그리고 n 값이 바뀌면 r도 바뀌게 된다. 하지만, a=7일 때 r의 최대값인 rmax=42이다.
3≤a≤1000일 때, rmax의 합계(∑rmax)를 구하시오.
--------------------------------------------------------------------------
어렵지 않아 보이지만 실행 시간이 많이 소요되는 문제이다. 나누는 수가 a2이기 때문에 나머지를 확인하기 위해 검증하는 범위를 a2번까지 설정해야 했기 때문이다.
그리고, 나머지 함수의 특성을 살려서 적용해야지 문제에서 제시한 그대로 코딩했을 때에는 숫자가 기하급수적으로 커지면서 실행시간이 매우 많이 필요하게 되었다.
나머지 함수의 곱셈 특징((a*b)%c=(a%c)*(b%c))을 활용하여, 거듭제곱의 경우 분산해서 계산하도록 코드를 개선했다. 즉, a7=a*a2*a4, a9=a*a8과 같은 형태로 나누고, 각각에 나머지 함수를 적용해서 숫자가 최대한 커지지 않도록 만들었다.
그렇게 개선했어도 실행시간은 많이 필요했으며(100까지 7초, 200까지 58초, 300까지 173초, 400까지 360초, 500까지 628초, 600까지 942초, 700까지 1365초, 800까지 1777초, 900까지 2415초, 1000까지 3043초로 총 3시간 필요), 이 방식보다는 좀 더 빠른 형태의 수학에 기반한 해법이 있을 것 같다.