Cod sursa(job #3221333)

Utilizator Wolf98Vlad Munteanu Wolf98 Data 6 aprilie 2024 19:48:57
Problema Ridicare la putere in timp logaritmic Scor 100
Compilator cpp-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <bits/stdc++.h>

using namespace std;

int MOD = 1999999973;

long long exp(long long N, long long P) {
    long long ans = 1;
    
    while (P > 0) {
        // Cat timp nu sunt pe cazul N ^ 0
        
        if (P % 2 == 0) {
            // Sunt pe cazul N ^ P = (N ^ 2) ^ (P / 2)
            N = (N * N) % MOD;
            P = P / 2;
        } else {
            // Sunt pe cazul N ^ P = (N ^ 2) ^ ((P - 1) / 2) * N
            
            // N ul extra se duce in answer
            ans = (ans * N) % MOD;
            
            // Restul devine la fel ca in cazul unde P este par
            N = (N * N) % MOD;
            P = (P - 1) / 2;
        }
    }
    
    return ans;
}

int main() {
    ifstream fin ("lgput.in");
    ofstream fout ("lgput.out");
    int a, b;
    fin >> a >> b;
    fout << exp(a, b);
    return 0;
}