P009 - Cure Sunny's Depression

Task: Find $ \left(\displaystyle\sum_{k=a}^b 2^k\right) \text{ mod } M $ ($ M = 1000000007 $).

Subtask 1 (Brute Force)

For every integer $ k $ from $ a $ to $ b $, compute $ 2^k $ naively and add it to the result.
You should compute $ 2^k $ by iteration (looping from $ 1 $ to $ k $) instead of using the built-in pow function, since there will be overflow for sufficiently large input.

Apply the following properties of modular arithmetic:

• $ (A + B) \text{ mod } M = (A \text{ mod } M + B \text{ mod } M) \text{ mod } M $
• $ AB \text{ mod } M = (A \text{ mod } M)(B \text{ mod } M) \text{ mod } M $

Time Complexity: $ O(b^2) $

Subtask 2

Solution 1

We can use binary exponentiation to compute $ 2^k $ in $ O(\log{k}) $ instead of $ O(k) $.

Time Complexity: $ O(b \log{b}) $

Solution 2

We can precompute powers of $ 2 $ modulo $ M $ up to $ b $ in $ O(b) $.
Define $ p[k] = 2^k \text{ mod } M $. Then $$ p[k] = \begin{cases} 1 & \text{ if } k = 0 \\ (p[k-1] \times 2) \text{ mod } M & \text{ if } k > 0 \end{cases} $$ We only need to calculate the sum of $ p[a..b] $ modulo $ M $.

Time Complexity: $ O(b) $

Subtask 3 (Full Solution)

Let us ignore $ \text{mod } M $ for now.

Let $ S(n) = \displaystyle\sum_{k=0}^n 2^k $. Applying the idea of prefix sum (or partial sum), the sum we want is $ S(b) $ if $ a = 0 $, otherwise $ S(b) - S(a-1) $.
Observe $ S(n) $ in binary notation. It is $ \underbrace{1 \ldots 11}_{n+1 \text{ ones}} $ $ (= 1_2 + 10_2 + 100_2 + \ldots + 1 \underbrace{0 \ldots 00}_{n \text{ zeros}}) $. If we add $ 1 $ to $ S(n) $, it becomes $ 1 \underbrace{0 \ldots 00}_{n+1 \text{ zeros}} $ in binary, which is equivalent to $ 2^{n+1} $.

Hence we have the following identity: $$ S(n) = \displaystyle\sum_{k=0}^n 2^k = 2^{n+1} - 1 $$

We are to compute $ [S(b) - S(a-1)] \text{ mod } M $ $ = [(2^{b+1} - 1) - (2^{a-1+1} - 1)] \text{ mod } M $ $ = (2^{b+1} - 2^a) \text{ mod } M $.
Magically, it also handles the case $ a = 0 $ because $ S(-1) = 0 $.

We can compute the required powers of 2 using binary exponentiation.
However, note that $ (2^{b+1} - 2^a) \text{ mod } M $ can be negative (in C++). Therefore, apply the property $ (A - B) \text{ mod } M = (A \text{ mod } M - B \text{ mod } M + M) \text{ mod } M $.

Time Complexity: $ O(\log{b}) $

P010 - Cure Justin's Depression

Find $ x_i $, i.e. the modular inverse of $ J_i $, using the Extended Euclidean algorithm.

$ x_i $ exists iff (if and only if) $ \gcd(J_i, K_i) = 1. $

Time Complexity: $ O(n \log(\max(J_i, K_i))) $

P011 - Cure Jono's Depression

Solution 1

Note that $ K \mid \displaystyle\prod_{i=1}^N a_i \iff \displaystyle\prod_{i=1}^N a_i \equiv 0 \, (\text{mod } K) $.
Compute the product of $ a $ modulo $ K $ and check if it is $ 0 $.

Time Complexity: $ O(N) $

Solution 2

If $ d \mid k $ and $ d \mid a_x $ and $ \dfrac{k}{d} \mid \displaystyle\prod_{i=x+1}^N a_i $, then $ k \mid \displaystyle\prod_{i=x}^N a_i $.
It is optimal to choose $ d = \gcd(a_x, k) $.
Set $ k = K $ initially. For $ x $ from $ 1 $ to $ N $, set $ k = \dfrac{k}{\gcd(a_x, k)} $. If $ k = 1 $ at the end then $ K \mid \displaystyle\prod_{i=1}^N a_i $.

Time Complexity: $ O(N \log(\max(K, a_i))) $