HackerRank Number Theory – Fun with 1010

Challenge: Fun with 1010

Subdomeniu: Number Theory (number-theory)

Scor cont: 120.0 / 120

Submission status: Accepted

Submission score: 1.0

Submission ID: 464775662

Limbaj: python3

Link challenge: https://www.hackerrank.com/challenges/fun-with-1010/problem

Cerinta

When you look at photographs of watches and clocks, you'll find that they almost always show the time 10:10. There are lots of theories and even urban legends about this. For example, when showing 10:10, the hands look like a smile, and so you are more inclined to buy the watch or clock :D (a form of [subliminal advertising](http://en.wikipedia.org/wiki/Subliminal_stimuli#Consumption_and_television)).

Now, you are given $N$ and $M$. You are to find the number of sequences $A_1, A_2, \ldots, A_N$ such that:

- $A_1$ is a number of the form $1010^K$ for some $1 \le K \le M$,
- If $P = A_2 \cdot A_3 \cdots A_N$, then $A_1$ is divisible by $P$, and $P$ is divisible by $1010$, and
- $A_2, A_3, \ldots, A_N$ are squarefree.

Since the number can be very large, only give the number modulo $2000003$.

**Input Format**  
The first line of input contains a single integer $T$, which is the number of test cases. The following lines contain the test cases.

Each test case consists of one line containing two integers, $N$ and $M$.

**Constraints**  
$1 \le T \le 10^5$  
$2 \le N \le M \le 10^{12}$  

**Output Format**  
For each test case, output a single line containing the answer.

**Sample Input**  

    2
    2 3
    3 3

**Sample Output**  

    3
    62

**Explanation**  
For the first test case, the possible sequences are:  
$\{1010, 1010\}$,  
$\{1020100, 1010\}$,  
$\{1030301000, 1010\}$

Cod sursa

# Enter your code here. Read sys.stdin.readline from STDIN. Print output to STDOUT
import sys

mod = 2000003
factorial_cache = [1, 1]
inverted_factorial_cache = [1, 1]
cache_two = {}
cache_ss = {}

def f(n):
    global factorial_cache
    if n >= len(factorial_cache):
        old_len = len(factorial_cache)
        new_len = max(1 + n, len(factorial_cache) * 11 // 10)   
        factorial_cache += [0] * (new_len - old_len)
        for i in range(old_len, new_len):
            factorial_cache[i] = factorial_cache[i - 1] * i % mod
    return factorial_cache[n]

def inv_f(n):
    global inverted_factorial_cache
    if n >= len(inverted_factorial_cache):
        old_len = len(inverted_factorial_cache)
        new_len = max(1 + n, len(inverted_factorial_cache) * 11 // 10)   
        inverted_factorial_cache += [-1] * (new_len-old_len)
    if inverted_factorial_cache[n] < 0:
        inverted_factorial_cache[n] = pow(f(n), mod - 2, mod)
    return inverted_factorial_cache[n]
        
def Cnk(n, k):
    if n < k:
        return 0
    return f(n) * inv_f(k) * inv_f(n - k) % mod 

def CnkBigP(n, k):
    zero = False
    N = n
    K = k
    while N > 0:
        NN = N % mod
        KK = K % mod
        if NN < KK:
            zero = True
            break
        N //= mod
        K //= mod
    if zero:
        return 0
    result = 1
    N = n
    K = k
    while N > 0:
        NN = N % mod
        KK = K % mod
        result *= Cnk(NN, KK)
        result %= mod
        N //= mod
        K //= mod
    return result

def t(n):
    global cache_two
    if n not in cache_two:
        cache_two[n] = pow(2, n, mod)
    return cache_two[n]

def ss(n):
    if n in cache_ss:
        return cache_ss[n]
    n2 = n + n
    n3 = n2 + n
    result = (n * t(n2 - 1) - (n2 - 1) * CnkBigP(n2 - 2, n - 1)) % mod
    cache_ss[n] = (3 * (t(n - 1) - 1) * result - n * t(n3 - 2) + t(n - 1) * n3 - n, (t(n3) - 3 * t(n2) + 3 * t(n) - 1))
    return cache_ss[n]

T = int(sys.stdin.readline())
for _ in range(T):
    N, M = map(int, sys.stdin.readline().split())
    n = N - 1
    s, c = ss(n)
    result = (s + c * (M + 1 - n)) % mod
    print(result)