Jak się uczyć na podstawie takiego zadania?
https://youtu.be/QgLyXYmFQeU?t=2019

——-
Kod C++ programu Kulki, który jest omówiony w powyższym filmie i który otrzymuje 100%

#include <bits/stdc++.h>
using namespace std;
const int ILORAZ_WARTOSC = 1e9+7;
long long SzybkiePotegowanie (long long podstawa, long long wykladnik) {
long long potega_polowy;
long long wynik;
if (wykladnik == 0)
return 1;
potega_polowy = SzybkiePotegowanie (podstawa, wykladnik/2);
wynik = potega_polowy * potega_polowy;
wynik = wynik % ILORAZ_WARTOSC;
if ( (wykladnik%2) == 1 ) {
wynik = wynik * podstawa;
wynik = wynik % ILORAZ_WARTOSC;
}
return wynik;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int liczba_pytan, liczba_kulek;
long long int wynik;
int i;
cin >> liczba_pytan;
for (i=1; i<=liczba_pytan; ++i) {
cin >> liczba_kulek;
wynik = SzybkiePotegowanie (liczba_kulek,liczba_kulek);
wynik = wynik - liczba_kulek;
wynik = wynik + ILORAZ_WARTOSC;
wynik = wynik % ILORAZ_WARTOSC;
cout << wynik << "\n";
}
return 0;
}

——–
——–

——–
——–
Poniżej dodatkowo kod C++, który wykonuje szybkie potęgowanie bez udziału rekurencji – również otrzymuje 100% z zadania.

#include <bits/stdc++.h>
using namespace std;
const int ILORAZ_WARTOSC = 1e9+7;
long long SzybkiePotegowanie (long long podstawa, long long wykladnik) {
long long wynik;
long long potega_podstawy;
potega_podstawy = podstawa;
wynik = 1;
while (wykladnik > 0) {
if ( (wykladnik%2) == 1 ) {
wynik = wynik * potega_podstawy; 
wynik = wynik % ILORAZ_WARTOSC;
}
potega_podstawy = potega_podstawy * potega_podstawy;
potega_podstawy = potega_podstawy % ILORAZ_WARTOSC;
wykladnik = wykladnik / 2;
}
return wynik;
}
int main() {
ios_base::sync_with_stdio(0);
cin.tie(0);
cout.tie(0);
int liczba_pytan, liczba_kulek;
long long int wynik;
int i;
cin >> liczba_pytan;
for (i=1; i<=liczba_pytan; ++i) { cin >> liczba_kulek;
wynik = SzybkiePotegowanie (liczba_kulek,liczba_kulek);
wynik = wynik - liczba_kulek;
wynik = wynik + ILORAZ_WARTOSC;
wynik = wynik % ILORAZ_WARTOSC;
cout << wynik << "\n";
}
return 0;
}

——–
——–

——–
——–
Poniżej dodatkowo kod Python, który wykonuje szybkie potęgowanie rekurencyjne

def szyb_modpot(liczba, pot):
potega_liczby = liczba
wynik = 1
while pot > 0:
if pot % 2 == 1:
wynik = wynik * potega_liczby
# wynik %= 1000000007
potega_liczby = potega_liczby * potega_liczby
potega_liczby = potega_liczby % 1000000007
pot = pot // 2
return wynik
for x in range(int(input())):
n = int(input())
wynik = szyb_modpot(n, n) -n + 1000000007
wynik %= 1000000007
print(wynik)