Cod sursa(job #3298877)

Utilizator tudorboscuTudor Boscu tudorboscu Data 2 iunie 2025 20:44:53
Problema Ridicare la putere in timp logaritmic Scor 0
Compilator c-64 Status done
Runda Arhiva educationala Marime 0.83 kb
#include <stdio.h>
#include <stdint.h>
#include <stdlib.h>

#define MODULO 1999999973

uint64_t exponentiere_rapida(uint64_t a, uint64_t b)
{
    uint64_t res = 1;
    a = a % MODULO;  //in caz ca sunt numere prea mari

    while(!b)
    {
        if (b % 2 == 1)
        {
            res*=a;
            res = res % MODULO; 
        }
        b = b >> 1; 
        a = a * a;
        b = b / 2;
    }

    return res;
}

int main(void)
{
    // printf("Starttt exp.\n");
    
    FILE *fin = NULL;
    if ((fin = fopen("lgput.in", "r")) == NULL){
        exit(-1);
    }
    FILE *fout = NULL; fopen("lgput.out", "w");
    if ((fin = fopen("lgput.out", "w")) == NULL){
        exit(-1);
    }


    uint64_t a, b;
    fscanf(fin, "%llu %llu", &a, &b);
    uint64_t res = exponentiere_rapida(a, b);
    fprintf(fout, "%llu", res);

    return 0;
}