|
Titlul: O metodă foarte ciudată de a calcula puterile lui 2 modulo 2 10^9+7 Scris de: Alexa Sergiu din Februarie 08, 2019, 13:10:52 Am găsit în rezolvarea unei probleme acest subprogram care calculează 2^n modulo 10^9+7.
Cod: const unsigned long long mod = 1000000007; unsigned long long mul (long long a, long long b) { return (a * b) % mod; }; unsigned long long pw (long base, long exponent) { int result = 1; for (int bit=0;(1 << bit) <= exponent; bit++) { if (exponent & (1 << bit)) { result = mul (result, base); } base = mul (base, base); } return result; }; Îmi poate cineva explica, vă rog, când condiția Cod: exponent & (1 << bit) se evaluează la un număr diferit de 0? Știu că & este conjuncție pe biți, dar asta nu mă lămurește. |