F013B. Codificació de Gödel P41073


Statement
 

pdf   zip

html

[r] Considereu la seqüència infinita de nombres primers: p0 = 2, p1 = 3, p2 = 5, etcètera. Per a cada nombre s de n xifres s = sos1sn−1, la seva codificació de Gödel es defineix com

 
0 ≤ i < n
pisi ⁠ ⁠ = ⁠ ⁠ p0s0 · p1s1 … pn−2sn−2 · pn−1sn−1

Per exemple, la codificació de Gödel de 4031 és 24 · 30 · 53 · 71 = 16 · 1 · 125 · 7 = 14000.

Feu un programa que llegeixi nombres i escrigui la seva codificació de Gödel.

Entrada

L’entrada consisteix en diversos nombres, amb possibles zeros a l’esquerra. Els nombres primers necessaris per a les codificacions dels nombres donats són tots més petits que 4 · 106.

Sortida

Per a cada nombre de l’entrada, cal escriure una línia amb aquell nombre i la seva codificació, seguint el format de l’exemple. Suposeu que les codificacions no tindran mai sobreeiximents.

Observacions

Alguns dels nombres donats seran molt llargs, o tindran zeros a l’esquerra. Feu servir strings per llegir i tractar aquests nombres. A més, el vostre programa ha de ser eficient. Useu el garbell d’Eratòstenes per calcular tots els primers fins a 4 · 106 al principi del programa.

Public test cases
  • Input

    4031
    010
    101
    808
    00
    00000001
    11111111
    10301040
    0
    1
    9
    20200000000000000000000000000012
    

    Output

    4031 -> 14000
    010 -> 3
    101 -> 10
    808 -> 100000000
    00 -> 1
    00000001 -> 19
    11111111 -> 9699690
    10301040 -> 229682750
    0 -> 1
    1 -> 2
    9 -> 512
    20200000000000000000000000000012 -> 217944700
    
  • Information
    Author
    Professorat de P1
    Language
    Catalan
    Official solutions
    C++
    User solutions
    C++