Soluție HackerRank pentru Fun with 1010, subdomeniul Number Theory, în Python 3. Include cerința formatată, exemple, explicația pașilor și cod sursă.
- Problemă: Fun with 1010
- Domeniu: Number Theory
- Limbaj: Python 3
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
Cerință
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 😀 (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, …, A_N such that:
- A_1 is a number of the form 1010^K for some 1 ≤ K ≤ M,
- If P = A_2 · A_3 ·s A_N, then A_1 is divisible by P, and P is divisible by 1010, and
- A_2, A_3, …, 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 ≤ T ≤ 10^5
2 ≤ N ≤ M ≤ 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 sursă
# 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)