Se considera urmatoarea functie recursiva, care calculeaza produsul a doua numere modulo M folosind dublare si injumatatire:
long long f(long long a, long long b) {
if (a == 0) return 0;
else if (a & 1) return (b + f(a ^ 1, b)) % M;
else return f(a >> 1, b << 1);
}
Se poate demonstra ca f(a,b) calculeaza exact (a*b) mod M.
Se considera apoi codul:
long long suma = 0;
for (long long i = 0; i < Count; i++) {
suma += f(i, i);
suma %= M;
}
Care este valoarea finala a lui suma, pentru un modul M si un numar de pasi Count date?
- Date de intrare
- Se citesc pe o singura linie doua numere intregi M si Count.
- Date de iesire
- Se afiseaza un singur numar intreg: valoarea finala a lui suma.
- Restrictii
- 2 <= M <= 10^9 1 <= Count <= 10^11
Exemple
Exemplul 1
Intrare
137 2000000000
Iesire
4
Exemplul 2
Intrare
5 1
Iesire
0