Coding Challenge Solution

solution.c

#include<stdio.h>

// Modular Exponentiation (https://www.geeksforgeeks.org/modular-exponentiation-power-in-modular-arithmetic/)

unsigned long long mod_exp(unsigned long long x, unsigned long long y, unsigned long long p)
{
    unsigned long long res = 1;
    x = x % p;
    while (y > 0)
    {
        if (y & 1)
            res = (res*x) % p;
        y = y>>1;
        x = (x*x) % p;  
    }
    return res;
}


/*
 M = 90555607 = 337 * 379 * 709
 for every integer x >= 709, x! (mod M) = 0, because x!=x*(x-1)*...*709*...*379*...*337*...*3*2*1
 that yields that from a certain index k, X(n+2) = p * X(n+1) (mod M), which is a geometric sequence
 S(n) = X(0) + X(1) + X(2) + X(2) * p + X(2) * p * p + X(2) * p * p * p ...  (mod M)
 X(2) = p * X(1) + X(1)  (mod M)
 S(n) = X(0) + X(1) + X(1) * (1+p) * (1 + p + p * p + p * p * p ...)  (mod M)
 S(n) = X(0) + X(1) + X(1) * (1+p) * ( p ** (n-1) - 1 ) / (p - 1)  (mod M)
 
 division by (p-1) becomes multiplication by its multiplicative inverse (modulo M)
*/
int main()
{
    unsigned long long M = 90555607L;
    unsigned long long x0 = 406;
    unsigned long long x1 = 709;
    unsigned long long n = 133713371337L;
    unsigned long long p = 101;
    unsigned long long inv = 51616696L; // inverse of (p-1) (mod M), can be calculated using the Extended Euclidean Algorithm, Euler Theorem, or even an online calculator

    printf("%lld\n", (x0 + x1 + x1 * (p + 1) * (mod_exp(p, n-1, M) - 1) * inv) % M); // Solution en une ligne
}