Return to Revisions

The obvious with this code is the lack of structure. There are two main computations, given that we've already spotted that we can add all the exponents and perform a single exponentiation with the sum:

• Finding the Lth and Rth odd-length palindromic numbers
• Modular exponentiation

Each of these should be separate - independently testable - functions; main() then only needs to read input, call the functions and print output.

Let's look at the exponentiation first. Putting your code into a function with reasonable names gives

long modexp(int base, int power, int modulus)
{
    long product = 1;
    for (int j = 1;  j <= power;  ++j)
        product = product * base % modulus;
    return product;
}

This is pretty slow, as it has to perform power multiplications. It's better to implement a binary exponentiaton, which scales as the log of the power:

long modexp(int base, int power, int modulus)
{
    long product = 1;
    while (power) {
        if (power % 2) {
            product = product * base % modulus;
        }
        base = 1L * base * base % modulus;
        power /= 2;
    }
    return product;
}

With that first easy win under our belt, let's turn our attention to the palindromes.

We don't need to iterate through all the possible palindromes. The pattern is quite simple: for a given number n, the n th odd-length palindrome is simply n followed by the reverse of n/10.

That's quite easy to compute without iterating:

int odd_palindrome(int n)
{
    int palindrome = n;
    while ((n /= 10)) {
        palindrome = palindrome * 10 + n % 10;
    }
    return palindrome;
}

We can now create a function to calculate the required function of the sequence of palindromes:

long compute_result(int left, int right)
{
    int sum = 0;
    for (int i = left + 1;  i <= right;  ++i) {
        sum += odd_palindrome(i);
    }
    return modexp(odd_palindrome(left), sum, 1000000007);
}

Having tested these functions, we can put it all together, getting something which is more efficient and easier to follow than the posted code:

#include <stdio.h>

const int result_modulus = 1000000007;

static long modexp(long base, int power, int modulus)
{
    long product = 1;
    while (power) {
        if (power % 2) {
            product = product * base % modulus;
        }
        base = base * base % modulus;
        power /= 2;
    }
    return product;
}

static int odd_palindrome(int n)
{
    int palindrome = n;
    while ((n /= 10)) {
        palindrome = palindrome * 10 + n % 10;
    }
    return palindrome;
}

static long compute_result(int left, int right)
{
    int sum = 0;
    for (int i = left + 1;  i <= right;  ++i) {
        sum += odd_palindrome(i);
    }
    return modexp(odd_palindrome(left), sum, result_modulus);
}

int main(void)
{
    int ntests;
    if (scanf("%d", &ntests) != 1) {
        return 1;
    }

    while (ntests --> 0) {
        int left, right;
        if (scanf("%d %d", &left, &right) != 2) {
            return 1;
        }
        printf("%ld\n", compute_result(left, right));
    }
}