RSS Feed

토션트 계단 수열

Problem 337

출제 일시 : 2021-06-19 00:02:03

{a1, a2,..., an}는 길이 n의 정수 수열로 다음 조건을 만족합니다:

  • a1 = 6
  • 모든 1 ≤ i < n에서 : φ(ai) < φ(ai+1) < ai < ai+11

S(N)은 anN인 수열의 개수입니다.
예를 들어, S(10) = 4 이고: 각 수열은 {6}, {6, 8}, {6, 8, 9}, {6, 10}입니다.
S(100) = 482073668이고 S(10 000) mod 108 = 73808307 임을 확인할 수 있습니다.

S(20 000 000) mod 108를 구하세요.

주)1 φ 는 오일러 토션트(totient) 함수입니다.


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