Funkcije

Osnovne informacije

Omejitve
  • Čas: 4 s
  • Spomin: 128 MB
Avtor:
  • Janez Brank
  • UPM 2013

Pošlji rešitev



Tvoji rezultati.
Nisi poslal še nobene rešitve.
Več »

Pri tej nalogi se bomo ukvarjali s funkcijami, ki slikajo iz pozitivnih celih števil v množico \mathbb{Z}_{2017} (torej množico celih števil od 0 do 2016, v kateri seštevamo in množimo tako, da po vsaki operaciji obdržimo le ostanek po deljenju rezultata z 2017) in za katere velja f(1) = 1.

Za funkciji f in g je njuna konvolucija takšna funkcija f*g, za katero velja:

  • za vsak n je (f*g)(n) = \sum_{d \colon d | n} f(d) g(n/d).

Vsota gre torej po vseh deliteljih števila n. (Še enkrat opozorimo na to, da naše funkcije slikajo v \mathbb{Z}_{2017}, zato tudi v tej definiciji pri seštevanju in množenju gledamo le ostanke po deljenju z 2017.)

Definirajmo še enotsko funkcijo e(n) takole:

  • e(1) = 1
  • e(n) = 0 za vsak n > 1.

Rekli bomo, da je g inverz funkcije f, če je f*g = e.

Napiši program, ki prebere prvih n vrednosti neke funkcije f, torej f(1), \ldots, f(n), in izračuna prvih n vrednosti njenega inverza, torej g(1), \ldots, g(n). (Tudi g mora seveda ustrezati vsem omejitvam z začetka te naloge: g(1) = 1 in za vsak k mora biti g(k) \in \mathbb{Z}_{2017}.)

Vhodni podatki

V prvi vrstici je celo število n, druga vrstica pa vsebuje s presledki ločena števila f(1), f(2), ..., f(n).

Omejitve vhodnih podatkov

  • 1 \leq n \leq 10^4
  • 0 \leq f(k) < 2017 za vsak k od 1 do n

Izhodni podatki

Izpiši n števil, vsako v svojo vrstico: najprej g(1), nato g(2), ..., nazadnje še g(n).

Primer

Vhod

10
1 1 1 1 1 1 1 1 1 1

Izhod

1
2016
2016
0
2016
1
2016
0
0
1
Tip: Log in to
  • submit and test your solution
  • post or read questions and answers about this task