제곱수의 나머지 합 구하기

$n = 8 k + r$ ($k$는 음이 아닌 정수, $r = 0 , 1 , 2 , \cdots , 7$)로 놓으면 $n ^{2} = 64 k ^{2} + 16 kr + r ^{2} = 8 ( 8 k ^{2} + 2 kr ) + r ^{2}$ 이므로 $f ( n )$은 $r ^{2}$을 $8$로 나눈 나머지와 같다. $r = 0 , 1 , 2 , 3 , 4 , 5 , 6 , 7$일 때 $r ^{2}$을 $8$로 나눈 나머지는 차례로 $0 , 1 , 4 , 1 , 0 , 1 , 4 , 1$ 이므로 $f ( n )$의 값은 $8$개씩 반복되고, 연속한 $8$개의 합은 $0 + 1 + 4 + 1 + 0 + 1 + 4 + 1 = 12$ $100 = 8 \cdot 12 + 4$이므로 $f ( 1 ) + f ( 2 ) + \cdots + f ( 96 ) = 12 \cdot 12 = 144$ $f ( 97 ) + f ( 98 ) + f ( 99 ) + f ( 100 ) = f ( 1 ) + f ( 2 ) + f ( 3 ) + f ( 4 ) = 1 + 4 + 1 + 0 = 6$ 따라서 구하는 값은 $144 + 6 = 150$이다.