RSS Feed

나머지 연산의 합

Problem 326

출제 일시 : 2021-01-25 00:05:04

$a_n$은 다음과 같이 재귀적으로 정의되는 수열입니다:$\quad a_1=1,\quad\displaystyle a_n=\biggl(\sum_{k=1}^{n-1}k\cdot a_k\biggr)\bmod n$.

수열 $a_n$의 첫 10개 항은 다음과 같습니다: 1,1,0,3,0,3,5,4,1,9.

다음 조건을 만족하는 쌍 (p,q)의 개수를 f(N,M)이라 합니다:

$$ \def\htmltext#1{\style{font-family:inherit;}{\text{#1}}} 1\le p\le q\le N \quad\htmltext{ 이고 }\quad\biggl(\sum_{i=p}^qa_i\biggr)\bmod M=0 $$

f(10,10)=4 이고, 네 쌍은 (3,3), (5,5), (7,9), (9,10) 입니다.

또한, f(104,103)=97158 입니다.

f(1012,106) 값을 구하세요.


로그인 하시면 답안을 제출할 수 있고,
정답을 맞히신 분들은 댓글을 달거나 볼 수 있습니다.