Bash Plays with Functions (Codeforces 757E)
Tags: Others, combinatorics

Bash got tired on his journey to become the greatest Pokemon master. So he decides to take a break and play with functions.Bash defines a function f0(n), which denotes the number of ways of factoring n into two factors p and q such that gcd(p, q) = 1. In other words, f0(n) is the number of ordered pairs of positive integers (p, q) such that p·q = n and gcd(p, q) = 1.But Bash felt that it was too easy to calculate this function. So he defined a series of functions, where fr + 1 is defined as:Where (u, v) is any ordered pair of positive integers, they need not to be co-prime.Now Bash wants to know the value of fr(n) for different r and n. Since the value could be huge, he would like to know the value modulo 109 + 7. Help him!

Input: The first line contains an integer q (1 ≤ q ≤ 106) — the number of values Bash wants to know.Each of the next q lines contain two integers r and n (0 ≤ r ≤ 106, 1 ≤ n ≤ 106), which denote Bash wants to know the value fr(n).

Output: Print q integers. For each pair of r and n given, print fr(n) modulo 109 + 7 on a separate line.


Sample Inputs:
5
0 30
1 25
3 65
2 5
4 48

Sample Outputs:
8
5
25
4
630

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (m + 1) + v

def fast_prime_factorization(n):
    d = [(i + 1) % 2 * 2 for i in range(n + 1)]
    (d[0], d[1]) = (0, 1)
    for i in range(3, n + 1):
        if d[i]:
            continue
        for j in range(i, n + 1, 2 * i):
            if not d[j]:
                d[j] = i
    return d
q = int(input())
mod = pow(10, 9) + 7
m = 20
l = pow(10, 6) + 5
dp = [1] * ((m + 1) * l)
for i in range(1, m + 1):
    dp[i] = 2
for i in range(1, l):
    for j in range(i * (m + 1) + 1, (i + 1) * (m + 1)):
        dp[j] = (dp[j - 1] + dp[j - m - 1]) % mod
d = fast_prime_factorization(l)
cnt = [0] * l
ans = ['1'] * q
for i in range(q):
    (r, n) = map(int, input().split())
    if n == 1:
        continue
    n0 = n
    while d[n] ^ n:
        cnt[d[n]] += 1
        n //= d[n]
    cnt[n] += 1
    n = n0
    ans0 = 1
    while d[n] ^ n:
        ans0 = ans0 * dp[f(r, cnt[d[n]])] % mod
        cnt[d[n]] = 0
        n //= d[n]
    ans0 = ans0 * dp[f(r, cnt[d[n]])] % mod
    cnt[n] = 0
    ans[i] = str(ans0)
sys.stdout.write('\n'.join(ans))

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def f(u, v):
    return u * (m + 1) + v

def fast_prime_factorization(n):
    d = [(i + 1) % 2 * 2 for i in range(n + 1)]
    (d[0], d[1]) = (0, 1)
    for i in range(3, n + 1):
        if d[i]:
            continue
        for j in range(i, n + 1, 2 * i):
            if not d[j]:
                d[j] = i
    return d
q = int(input())
mod = pow(10, 9) + 7
m = 20
l = pow(10, 6) + 5
dp = [1] * ((m + 1) * l)
for i in range(1, m + 1):
    dp[i] = 2
for i in range(1, l):
    for j in range(i * (m + 1) + 1, (i + 1) * (m + 1)):
        dp[j] = (dp[j - 1] + dp[j - m - 1]) % mod
d = fast_prime_factorization(l)
cnt = [0] * l
ans = ['1'] * q
for i in range(q):
    (r, n) = map(int, input().split())
    if n == 1:
        continue
    n0 = n
    while d[n] ^ n:
        cnt[d[n]] += 1
        n //= d[n]
    cnt[n] += 1
    n = n0
    ans0 = 1
    while d[n] ^ n:
        ans0 = ans0 * dp[f(r, cnt[d[n]])] % mod
        cnt[d[n]] = 0
        n //= d[n]
    ans0 = ans0 * dp[f(r, cnt[d[n]])] % mod
    cnt[n] = 0
    ans[i] = str(ans0)
ans = '\n'.join(ans).encode()
os.write(1, b'%s\n' % ans)

Solution (Python):
import sys, os, io
input = io.BytesIO(os.read(0, os.fstat(0).st_size)).readline

def make_graph(n, m):
    (x, s) = ([0] * (2 * m), [0] * (n + 3))
    for i in range(0, 2 * m, 2):
        (u, v) = map(int, input().split())
        s[u + 2] += 1
        (x[i], x[i + 1]) = (u, v)
    for i in range(3, n + 3):
        s[i] += s[i - 1]
    (G, W) = ([0] * m, [0] * m)
    for i in range(0, 2 * m, 2):
        j = x[i] + 1
        (G[s[j]], W[s[j]]) = (x[i ^ 1], i >> 1)
        s[j] += 1
    return (G, W, s)

def fast_prime_factorization(n):
    d = [(i + 1) % 2 * 2 for i in range(n + 1)]
    (d[0], d[1]) = (0, 1)
    for i in range(3, n + 1):
        if d[i]:
            continue
        for j in range(i, n + 1, 2 * i):
            if not d[j]:
                d[j] = i
    return d
q = int(input())
mod = pow(10, 9) + 7
l = pow(10, 6) + 5
(x, y, s) = make_graph(l, q)
m = 20
dp = [2] * (m + 1)
dp[0] = 1
d = fast_prime_factorization(l)
ans = ['1'] * q
for r in range(l + 1):
    for v in range(s[r], s[r + 1]):
        (n, i) = (x[v], y[v])
        if n == 1:
            continue
        ans0 = 1
        (la, c) = (1, 0)
        while n ^ 1:
            if la ^ d[n]:
                ans0 = ans0 * dp[c] % mod
                (la, c) = (d[n], 0)
            c += 1
            n //= d[n]
        ans0 = ans0 * dp[c] % mod
        ans[i] = str(ans0)
    for i in range(1, m + 1):
        dp[i] = (dp[i] + dp[i - 1]) % mod
sys.stdout.write('\n'.join(ans))