Problem H
Leynitölur
Languages
en
is
Jón has a list of his 100 favourite numbers, all integers in the interval from $0$ to $10^{18}$. He cares deeply about these numbers and doesn’t want anyone finding out about them. He has decided to encrypt the numbers, doing it in the following way:
-
He takes a value $x$ from his list.
-
He multiplies $x$ with the numbers $230\, 309\, 227$ and then adds the result to $68\, 431\, 307$. He then divides the result by $2^{64}$ and calls the remainder of the division $y$.
-
He now forgets the number $x$ and instead stores $y$ which is the encrypted value.
He did this to all his numbers in the list and now has 100 encrypted numbres. But he forgot the most important part: he has no idea how he can decrypt his numbers. Can you help him?
Input
The input contains a hundred integers, each an encrypted number, one on each line.
Output
Print one line for each encrypted number in the input. This line should contain the decrypted number, which is an integer between $0$ and $10^{18}$, or $0$ if you do now know what the decrypted number is. You can assume that there is exactly one number between $0$ and $10^{18}$ which is the decrypted version of the corresponding number in the input. I.e. if it is encrypted again, it becomes the value in the input.
Scoring
The solution will be run on a list of 100 encrypted numbers. The list is always the same and it will be shown here below. The solution gets 1 point for each value it decrypts.
Jón also gave the following information about the original list of numbers:
-
10 numbers are very small ($< 10$)
-
10 numbers are rather small ($< 1000$)
-
7 numbers are “Perfect numbers”
-
10 numbers are “Factorial values”
-
10 numbers are of the form $2^n$
-
10 numbers are “Fibonacci numbers”
-
10 numbers are “Catalan numbers”
-
10 numbers are “Motzkin numbers”
-
10 numbers are “Triangular numbers”
-
13 numbers are very big ($< 10^{18}$)
Explanation of Sample Input
In the sample input a list of 100 encrypted numbers is given, the one your solution will be tested on. The output in the sample gives an example of what your solution could print out. All values there, except three, are $0$.
On line 5 the output returned the number $6$. Let us try encrypting this number:
-
Multiply $6$ by $230\, 309\, 227$ to get $1\, 381\, 855\, 362$.
-
We then add $68\, 431\, 307$ to the result and get $1\, 450\, 286\, 669$.
-
Then we perform the division $1\, 450\, 286\, 669 / 2^{64}$ and get $0$ with the remainder $1\, 450\, 286\, 669$.
-
The remainder $1\, 450\, 286\, 669$ is thus the encrypted version of the number $6$.
If we look at line 5 in the input, then we find exactly the number $1\, 450\, 286\, 669$ which was the encrypted value Jói wanted to decrypt. The answer $6$ is thus correct and the solution gets one point for this value. It just so happens that the number $6$ is also both a “Perect number” and a very small number ($< 10$).
On line 38 of the input the solution returned the number $42$. Let us try encrypting this number:
-
Multiply $42$ by $230\, 309\, 227$ to get $9\, 672\, 987\, 534$.
-
We then add $68\, 431\, 307$ to the result and get $9\, 741\, 418\, 841$.
-
We then perform the division $9\, 741\, 418\, 841 / 2^{64}$ and get $0$ with the remainder $9\, 741\, 418\, 841$.
-
The remainder $9\, 741\, 418\, 841$ is thus the encrypted version of the number $42$.
If we look at line 38 of the input, it was the number $68\, 431\, 307$ that Jói wanted to decrypt. The answer $42$ is thus not correct, so the solution gets no points for this number.
On line 40 of the output the solution output the number $806\, 515\, 533\, 049\, 393$. Let us try to encrypt this number:
-
Multiply $806\, 515\, 533\, 049\, 393$ by $230\, 309\, 227$ to get $185\, 747\, 968\, 980\, 098\, 654\, 649\, 211$.
-
Then add $68\, 431\, 307$ to the result to get $185\, 747\, 968\, 980\, 098\, 723\, 080\, 518$.
-
Then perform the division $185\, 747\, 968\, 980\, 098\, 723\, 080\, 518 / 2^{64}$ to get $10\, 069$ with the remainder $7\, 702\, 901\, 917\, 247\, 859\, 014$.
-
The remainder $7\, 702\, 901\, 917\, 247\, 859\, 014$ is thus the encrypted version of $806\, 515\, 533\, 049\, 393$.
If we look at line 40 of the input, it was the number $7\, 702\, 901\, 917\, 247\, 859\, 014$ that Jói wanted to decrypt. The answer $806\, 515\, 533\, 049\, 393$ is thus correct and the solution gets one point for this number. It just so happens that $806\, 515\, 533\, 049\, 393$ is a “Fibonacci number”.
| Sample Input 1 | Sample Output 1 |
|---|---|
18223710894738859083 13206715060184165835 10185240380512959299 1931973892517323 1450286669 6021567682509141451 138714585961 422919574979260288 9635054942852 14552931137501048267 835746191368907 8770042884959775595 6164323997686895178 16905399806933083155 1311420849701858561 14908754392032399994 12890726524107255501 1180101699970319594 15800253748647522238 1680595896 11695533784197154595 88507174475 57876047284 3783748257302582136 2545702210039907996 83574680725067 6341068275406089675 3713883211570731520 16300997420262959118 214025703190 3698343441921813963 16814363719088675361 12393906174592036299 298740534 6517089663 14808221835 2622534442265585971 68431307 3863947716603339 7702901917247859014 47742441296 214256012417 2809041190924859584 615948277489187 759358988 5222818139880373393 1910905123 7910173006526044074 1160826935387 7726952018181579 529049761 218171269276 47051513615 92299468167589928 17357274356146956201 7414039778265390868 989668215 989170598000471499 13206654686002163147 14928293174154046923 18303861531118430445 17742860839300167228 1872021828363 11308186127620784250 36457289173 5883968300900284717 15319152107597547134 9473861667483854665 3981937021227917058 17960730271744214948 9741418841 1434140347029352907 5718061173776289753 9221431121542298880 7710162562126720459 12843829917114508059 13700707387741159706 71694600904 12137560070380009487 15469864720086085067 2426027911978121844 140557059777 15930479467699770909 16819631862868750397 11399132061084986557 4008544522317321026 3457167503216882366 29858391437908637 114301807899 9593390538144192759 407017019262885437 15420325124185009611 1219977442 1631220783811782091 27705538547 1450286669 1978326102387011019 1594237062672645103 11887301847946087637 2141214350 |
875611033061344128 137438953472 8944394323791464 8388608 6 1307674368000 602 1836311903 41835 355687428096000 3628800 451909860726587616 743301543085819453 263747951750360 679891637638612258 724066394573497037 55534064877048198 14544636039226909 192137918101841817 7 264118168634493448 384 251 61305790721611591 832721640469329331 362880 576460752303423488 2750016719520991 420196140727489673 929 6402373705728000 73007772802 288230376151711744 1 28 64 91482563640 0 16777216 806515533049393 207 930 885703806313795871 2674440 3 343059613650 8 848821429864631901 5040 33550336 2 947 204 400763223 108500229861914394 65346306570478875 4 4294967296 137438691328 121645100408832000 603441230355458022 13933569346707 8128 738009091801197773 158 212336130412243110 66368199913921497 179224005103730170 22944749046030949 205043723361104587 42 6227020800 822173150480239530 11130037491592671 72057594037927936 160500643816367088 139583862445 311 556704809728838604 4503599627370496 953467954114363 610 897145272235330422 182829778442895830 38756443662964566 426548945951821605 259695496911122585 129644790 496 150145796978065540 1767263190 144115188075855872 5 87178291200 120 6 8589869056 498522796180270956 541595904581297566 9 |
