Finding inverse

#include <stdint.h>
#include <stdlib.h>
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define LOOP(i,s,e) for (uint64_t i = (s); i < (e); i++)
#define SCAN(...) if (scanf(__VA_ARGS__) == 0) return EXIT_FAILURE

uint64_t mod = 998244353;

typedef struct{
    uint64_t f[64];
    uint64_t nb;
} factor_t;

factor_t factors(uint64_t n){
    factor_t f;
    f.nb = 0;
    for(uint64_t x = 2; x*x <= n; x++){
        // printf("test %ld %% %ld : ", n, x);
        while(n%x == 0){
            f.f[f.nb] = x;
            f.nb++;
            // printf("[completed, n : %ld --> %ld]: ", n, n/x);
            n /= x;
        }
        // printf("\n");
    }
    if (n > 1){
        f.f[f.nb] = n;
        f.nb++;
    }
    return f;

}

uint64_t phi(uint64_t m){
    factor_t f = factors(m);
    // LOOP(i, 0, f.nb)
    //     printf("%ld, ", f.f[i]);
    // printf("\n");
    uint64_t p = 0;
    uint64_t pa = 0;
    uint64_t i = 0;
    uint64_t acc = 1;
    while(i < f.nb){
        p = f.f[i];
        pa = 1;
        i++;
        while (f.f[i] == p && i < f.nb){
            i++;
            pa*=p;
        }
        acc *= pa * (p-1);
    }
    return acc;
}
uint64_t exp(uint64_t x, uint64_t n){
    if (n == 0){
        // printf("n == 0\n");
        return 1;
    }
    if (n % 2 == 0){ // even
        // printf("n(%ld) even\n", n);
        uint64_t sqrt_x = exp(x, n/2);
        return (sqrt_x * sqrt_x) % mod;
    }
    // odd
    // printf("n(%ld) odd\n", n);
    return (exp(x, n-1) * x) % mod;

}

uint64_t inv(uint64_t x){
    // printf("phi(%ld) = %ld\n", mod, phi(mod));
    return exp(x, phi(mod)-1);
}

uint64_t gcd(uint64_t a, uint64_t b){
    if (b == 0)
        return a;
    return gcd(b, a%b);
}

int main() {
    uint64_t a;
    SCAN("%ld %ld", &a, &mod);

    // main algo
    if (gcd(a, mod) != 1)
        printf("-1\n");
    else
        printf("%ld\n", inv(a));


    return EXIT_SUCCESS;
}

Test 1

Verdict: ACCEPTED

Test 2

Verdict: ACCEPTED

Test 3

Verdict: ACCEPTED

Test 4

Verdict: ACCEPTED

Test 5

Verdict: ACCEPTED

Test 6

Verdict: ACCEPTED

Test 7

Verdict: ACCEPTED

Test 8

Verdict: ACCEPTED

Test 9

Verdict: ACCEPTED

Test 10

Verdict: ACCEPTED

Test 11

Verdict: ACCEPTED

Test 12

Verdict: ACCEPTED

Test 13

Verdict: ACCEPTED

Test 14

Verdict: ACCEPTED