Project Euler Problem 97 Solution

Project Euler Problem 97 Statement

The first known prime found to exceed one million digits was discovered in 1999, and is a Mersenne prime of the form $2^{6972593} - 1$; it contains exactly $2\,098\,960$ digits. Subsequently other Mersenne primes, of the form $2^p - 1$, have been found which contain more digits.

However, in 2004 there was found a massive non-Mersenne prime which contains $2\,357\,207$ digits: $28433 \times 2^{7830457} + 1$.

Find the last ten digits of this prime number.

Solution

HackerRank Project Euler Problem 97 overview:

We are given a list $T$, $(1\le T\le 500,000)$ of4 integers, $A, B, C, D$ for the equation form $A\times B^C+D$ and need to find the last 12 digits of the sum of all numbers in the list.

Solution Summary

By using modular arithmetic and efficient exponentiation (pow() function) to calculate the last 12 digits of the large number without dealing with its full representation and keep a running sum. We print the 12-digit result with zero-fill.

Solution Detail

1. Initialization:

s = 0: Initializes a variable s to store the sum of the results.
m = 10¹²: Sets m to 10¹², which is used for modulo operations to retain only the last 12 digits.

2. Input and Calculation:

It iterates through a given number of test cases.
For each test case, it reads four integers: a, b, c, and d.
pow(b, c, m): This is the core of the solution. It calculates b raised to the power c modulo m. This built-in function efficiently computes the modular exponentiation without calculating the full result, significantly reducing the computation time and memory usage.
(a * pow(b, c, m) + d) % m: It performs the remaining arithmetic operations (multiplication, addition, and modulo) to get the result for the current test case and adds it to the sum s.

3. Output:

print("%012d" % (s % m)): Finally, it prints the last 12 digits of the total sum s with leading zeros if necessary.

Python Source Code

s = 0
m = 10**12
for _ in range(int(input())):
    a, b, c, d = map(int, input().split())
    s += (a * pow(b, c, m) + d) % m
print("%012d" % (s % m))