PROFBL- Editorial

general
1

PROBLEM LINK:

Practice

Contest

Author: Md Shahid

Tester: Md Shahid

Editorialist: Md Shahid

DIFFICULTY:

EASY

PREREQUISITES:

Maths, GP Series,

PROBLEM:

Given H, you need to print the sum of the series 1 + 71 + 72 + … + 7H. Since the result can be large, the answer should be printed modulo 109 + 7.

QUICK EXPLANATION:

Since the value of H is large, you need to use modular exponentiation to calculate the sum of the series. After calculating the numerator of the gp series, it should be divided by 6, which can done by multiplying with the modular inverse of 6.

EXPLANATION:

First we need to calculate the sum of the GP series given in the problem. We can do this by using the simple GP formula as

7^0+7^1+7^2+...+7^H = \cfrac {7^{H+1} - 1} {7-1}

But since H can be very large we can’t calculate this directly. We need to calculate the term 7H+1 of the numerator by using modular exponentiation. Then we need to subtract 1 from the result we calculated. Now we divide the numerator by 7 – 1 = 6, but as we are calculating the result MOD 109 + 7, we need to multiply the numerator by the modular multiplicative inverse of 6. Basically we need to find a number k such that

6k\;\equiv\;1\;\;(mod\;\;10^9+7)

Then k will be the modular multiplicative inverse of 6. We can use Fermat’s Little Theorem to calculate the value of k. By the theorem, if p is any prime number, then for any integer a ≤ p, we can write

a^{p-1}\;\equiv\;1\;\;(mod\;\;p)

From here we get that

a^{p-2}\;\equiv\;a^{-1}\;\;(mod\;\;p)

k\;\equiv\;6^{10^9+5}\;\;(mod\;\;10^9+7)

As before we will find k using the modular exponentiation we used earlier. Now we just need to multiply this k with the numerator we obtained in the earlier steps and get the result. You can find the solution below for implementation details.

AUTHOR’S AND EDITORIALIST’S SOLUTIONS:

Author’s and editorialist’s solution can be found here.

Tags:- ENCODING PROFBL modularexponentiation series gp dshahid380

2

Crucially missing from this editorial is the following information:

x^0 + x^1+x^2+ \cdots+x^n = \frac{x^{n+1}-1}{x-1}

(and x^0=1 always), which in this case is

1 + 7+7^2+ \cdots+7^n = \frac{7^{n+1}-1}{7-1}

This means we only need to find that big power, which can be done with exponentiation by squaring taking the modulus into account as we go, if you don’t have access to a pow(x,y,m) type function.

Since we are working \bmod 1000000007, we need to find a way to divide by 7-1=6 after finding the big power and subtracting 1. We do this by finding the number k such that 6k\equiv 1 \bmod 1000000007. k is then the modular inverse of 6, and we can multiply by k instead of dividing by 6.

Using Fermat’s little theorem (FLT) to find this is OK if we know the modulus is prime (as it is here); basically since we know from FLT that 6^{p-1} \equiv 1 \bmod p for p prime, we can see that k \equiv 6^{p-2} \bmod p will give the desired 6k \equiv 1 \bmod p. Otherwise we can more rapidly and generally find the inverse using the extended Euclidean algorithm.

My code