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)