Revizia anterioară Revizia următoare
Spargere2
Vom reţine un vector auxiliar cu următoarea semnificaţie:
- d[i] = suma maximă ce poate fi obţinută folosind primele i seifuri
Vom parcurge seifurile de la 1 la N, iar pentru fiecare seif i, avem câteva opţiuni:
- Deschid seiful i şi le ignor pe cele de dinainte.
- Deschid seiful i şi iau şi suma maximă obţinută prin folosirea primelor i - k seifuri.
- Nu deschid seiful i, deci iau suma maximă obţinută prin folosirea celor dinaintea sa, primelor i - 1 seifuri.
În concluzie, vom avea:
- d[i] = max( v[i], d[i - k] + v[i], d[i - 1] )
Rezultatul se găseşte în d[n].
Bacterii
După primul pas de multiplicare, numărul bacteriilor devine N * (N - 3) + N + 2, adică N * (N - 2) + 2, adică (N - 1) 2 + 1. Se demonstrează prin inducţie că după K paşi de multiplicare, numărul bacteriilor devine [ (N - 1) la 2K ] + 1.
Vom folosi mica teoremă a lui Fermat:
- aM-1 ≡ 1 (mod M), unde M este număr prim.
Vom avea 2K = (M - 1) * Q + R, deci:
- (a2)K (mod M) ≡ (a(M-1))q * (aR) (mod M) ≡ 2K * aR (mod M) ≡ aR (mod M)
Înlocuind a cu N-1 în relaţia de mai sus, obţinem [(N-1)2]K (mod M) ≡ (N-1)R (mod M). Vom calcula mai întâi R, ridicând la putere 2 la K şi reţinând restul împărţirii la M-1. Apoi, vom ridica la N-1 la puterea R, reţinând restul împărţirii la M.
Pitici5
Fibsmen