CSES - Lukujono
  • Time limit: 4.00 s
  • Memory limit: 128 MB

Fibonaccin lukujono (Fn)(F_n) on erittäin tunnettu lukujono, ja se määritellään seuraavasti:

  • F0=0F_0 = 0
  • F1=1F_1 = 1
  • Fn=Fn1+Fn2F_n = F_{n - 1} + F_{n - 2}, jos n2n \geq 2.

Paljon vähemmälle huomiolle on jäänyt Uolevinaccin lukujono (Un)(U_n), joka määritellään seuraavasti:

  • U0=0U_0 = 0
  • U1=1U_1 = 1
  • Un=Un/2+Un/3+Un/4+Un/5++Un/nU_n = U_{\lfloor n/2\rfloor} + U_{\lfloor n/3\rfloor} + U_{\lfloor n/4\rfloor} + U_{\lfloor n/5\rfloor} + \ldots + U_{\lfloor n/n\rfloor}, jos n2n \geq 2.

Merkintä x\lfloor x \rfloor tarkoittaa lukua xx pyöristettynä alaspäin kokonaisluvuksi.

Syöte

Syötteenä annetaan yksi kokonaisluku nn.

Tuloste

Tulosteen tulee olla luku UnU_n.

Rajat

  • 1n1051 \leq n \leq 10^5
  • Voit olettaa, että UnU_n on enintään 10910^9.

Esimerkki

Syöte:

10

Tuloste:

13

Selitys:

  • U1=1U_1 = 1
  • U2=U1=1U_2 = U_1 = 1
  • U3=U1+U1=2U_3 = U_1 + U_1 = 2
  • U5=U2+U1+U1+U1=4U_5 = U_2 + U_1 + U_1 + U_1 = 4
  • U10=U5+U3+U2+U2+U1+U1+U1+U1+U1=13U_{10} = U_5 + U_3 + U_2 + U_2 + U_1 + U_1 + U_1 + U_1 + U_1 = 13