최대 나머지 찾기

Project Euler의 120번 문제다. (스포일러 있음!)

http://projecteuler.net/index.php?section=problems&id=120

Let r be the remainder when (a1)ⁿ + (a+1)ⁿ is divided by a².

For example, if a = 7 and n = 3, then r = 42: 6³ + 8³ = 728 42 mod 49. And as n varies, so too will r, but for a = 7 it turns out that r_max = 42.

For 3 a 1000, find r_max.

문제 이해하기.

r이라는 숫자를 정하는데,주어진 양의 정수 a에 대해서, a-1의 n제곱과 a+1의 n제곱의 합을 a의 제곱으로 나눈 나머지를 r이라고 한다.
n이 바뀌면 r도 변할 것이다. 하지만, 어쨌든 r의 최대값은 존재한다.
a가 3부터 1000까지 변할 때, 각각의 경우에 대한 r의 최대값을 모두 더하여라.

*수식은 인터넷 익스플로러에서는 제대로 표현되지 않음. 파이어폭스에서만 제대로 표현됨.

문제 접근하기.
(a1)ⁿ + (a+1)ⁿ을 이항정리에 의해 전개하면 다음과 같다.
$\sum_{k=0}^{n} nCk a^{n-k} (-1)^k + \sum_{k=0}^{n}nCk a^{n-k}$ mod $a^2$
그런데, 이걸 mod $a^2$에서 계산하면, $a^2$보다 차수가 높은 항은 모두 나누어 떨어지고 1차항과 상수항만 남는다. 즉, 나머지는 다음과 같이 표현된다.
$(-1)^n +na(-1)^{n-1}+na+1$ mod $a^2$
-1의 차수를 맞춰주고 이 식을 정리하면 다음과 같다
$r= 1+(-1)^n + na(1-(-1)^n)$ mod $a^2$
n이 0부터 변화될 때, r이 어떻게 변하는지 조사하면
$r=2$ if n is even
$r=2na$ if n is odd
n이 짝수일 때와 홀수일 때 다르게 된다. n이 0일때는 당연히 2가 나머지가 되고, n이 1보다 큰 홀수라고 한다면, 주어진 a의 조건인 3부터 1000이라는 범위 내에서 2na는 2보다 더 크다. 이 문제에서는 최대값을 찾아야 하므로, n이 홀수인 경우만 생각하면 된다.

접근 1
최대값은?
문제는 r이 언제 최대가 되느냐이다. a는 주어진 값이고, n이 커질수록 r이 커질 것이다. 그렇다면, n이 최대값을 가질 때 r도 최대값을 가질 것이다. 따라서, r이 최대가 되는 경우는 n이 a보다는 홀수 중 가장 큰 홀수가 되는 경우이다.
a가 짝수라면 n=a-1인 경우
a가 홀수라면 n=a-2인 경우
이제, 다 더해보면 된다. a가 짝수인 경우 a=2k로 표현된다고 하고, k를 2부터 500까지 변화시키면 된다. a가 홀수인 경우는 a=2k+1로 표현된다고 하고, k를 1부터 499까지 변화시키면 된다.
r을 계산해서 다 더해보자.

하지만 이것은 답이 아니다. (여기까지 해서 모두 더해서 답을 입력해 보았지만 틀렸다더라...)

접근 2
좌절하다가 말고, 문득 생각난 것이 있다. n=a-1이나 n=a-2를 대입해 보자.
$2na=2(a-1)a=2a^2 -2a$
$2na=2(a-2)a=2a^2 - 4a$
여기서, 보면 $a^2$의 앞에 계수가 2가 붙어 있다. 하지만, 우리는 mod $a^2$에서 작업중이므로, a의 제곱항들은 0으로 취급되는 항들이다. a는 2보다 크므로, a의 제곱항 앞에 있는 계수를 2 대신 1로 바꾸더라도 답에는 영향이 없다. 그래서, 이번엔 r의 값을 $a^2 - 2a$(if a is even)과 $a^2 - 4a$(if a is odd)로 바꾸어 계산하였다.

하지만 이것도 답이 아니었다.

접근 3
어디서 틀렸을까. 나는 2na를 뚫어지게 쳐다보았다. 2가 마음에 걸렸다. n은 죄가 없다. 문제는 2인 것이다. 즉, n이 커질수록 나머지가 커지는 것이 아니라 2n이 커질수록 나머지가 커진다는 것을 생각했어야 했다. n은 a보다 커지는 것이 의미가 없지만, 만약 2n이 a보다 커지게 된다면 나머지는 오히려 작아질 것이다. 따라서, 2n이 a보다 크지 않은 최대의 정수가 되는 경우를 생각해 봐야 한다.
a가 짝수라고 하면 a=2k로 표현할 수 있을 것이다. 이 경우, n=k-1이 된다. 왜냐하면, 2n이 a보다 크지 않아야 하는데, a보다 크지 않은 최대의 정수인 2k-1은 2n으로 표시할 수가 없고, 따라서 그 다음으로 큰 정수인 2k-2가 되어야 한다. 이런 경우에는 n=k-1이 된다.
a가 홀수라고 하면 a=2k+1로 표현할 수 있을 것이다. 이 경우 n=k가 된다. 이유는 앞서 설명한 것과 같다.
이제, a=2k, n=k-1을 대입해서 k를 2부터 500까지 모두 더하고, a=2k+1, n=k를 대입해서 k를 1부터 499까지 모두 더한 다음, 두 값을 더하면 된다.
이때, a가 짝수인 경우 k를 1부터 더하기 시작하든 2부터 더하기 시작하든 관계가 없다. k=1인 경우에는 n=0이 되기 때문에 합에 영향을 주지 않기 때문이다. 따라서, 가우스의 합 공식을 이용하여 문제를 해결할 수 있다.