project euler #120: Square Remainders

Let r be the remainder when (a−1)ⁿ + (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−1)ⁿ + (a+1)ⁿ 을 a²로 나눴을때의 나머지라 하자; 예를 들면 a = 7이고 n = 3이면, r = 42(6³ + 8³ = 728 ≡ 42 mod 49)이다. 그리고 n이 달라지면, r,도 달라질테지만, 어쨌건간에 a = 7이 경우는 r의 최댓값은 42이다. 

3부터 1000까지 a가 변할때, 가능한 r의 최댓값의 합들을 구해라.

(a−1)ⁿ + (a+1)ⁿ을 잘 관찰하면 끝나는 문제입니다. 

 a의 제곱에 대한 나머지므로, 이 다항식에서 a의 찻수가 1이하인 것만 고려해주면 됩니다. n이 짝수일 때에는 a의 계수는 0이고, 상수 2만 남으니 이때의 r은 2만 가능합니다. 반면 n이 홀수일때에는, 이 다항식의 두 항 모두 a의 계수가 na이고, 상수항은 0이니 r은 2na입니다. 이때 r의 최댓값은 2na꼴에서 나오겠죠?

 1)a가 홀수일 경우를 생각해봅시다. a가 7이라던가... n이 홀수일 때만 고려합시다. 짝수일 때는 2밖에 안될테니까. r이 2n*7꼴일텐데 2n가 7로 나눈 나머지로 가질수 있는 값은 1부터 6까지입니다. 그 중 6이 가장 크죠? 이때의 n은 3입니다. 마찬가지로 a가 홀수면, 2n을 a로 나눴을때의 나머지는 0부터 a-1까지 가질 수 있는데(n을 1부터 a까지 변화시키면 됩니다.) r의 최댓값은 a(a-1)이 됩니다. a=2k+1일때 최대가 될 조건은 n=k(k가 홀수), n=k+a(k가 짝수)이고요.

 2)a가 짝수일 경우는, 이것도 예를 들어보죠. a를 16이라고 하면, n이 홀수일 경우를 고려해서 2na가 나올텐데, 2n을 16으로 나눈 나머지로 0,2,4,6,8,10,12,14가 되고 이 중 14일 경우가 가장 크겠죠?  즉 a가 짝수이면 2n을 a로 나눈 나머지는 0부터 a-2까지의 수 중 짝수만 가능하겠고, 고로 r의 최댓값은 a(a-2)가 됩니다. a=2k라 한다면 n=k-1(k가 짝수), n=2k-1(k가 홀수)일 때가 r이 최대가 됩니다.

이를 바탕으로 python으로 코드를 짰습니다.

sum([(i-2+(i%2))*i for i in range(3,1001)])

한줄?

한줄풀이는 처음이네요....

이건 보자마자 아이디어를 잡았네요. a를 예시로 들어가면서 일반화시키고...