Submission #46636067

---

Source Code Expand

from math import sqrt

MOD = 998244353

# Returns the factorization of n as a map {prime: multiplicity}
def factorize(n):
    factors = {}
    # Count the number of times 2 divides n
    while n % 2 == 0:
        if 2 not in factors:
            factors[2] = 0
        factors[2] += 1
        n //= 2
    # n must be odd at this point, so a skip of 2 can be used
    for i in range(3, int(sqrt(n)) + 1, 2):
        # While i divides n, count i and divide n
        while n % i == 0:
            if i not in factors:
                factors[i] = 0
            factors[i] += 1
            n //= i
    # If n is a prime greater than 2
    if n > 2:
        factors[n] = 1
    return factors

# Calculate the number of divisors for A^B
def numDivisors(A, B):
    factors = factorize(A)
    divisors = 1
    for key in factors:
        divisors *= (factors[key] * B + 1)
    return divisors

def solve(A, B):
    divisors = numDivisors(A, B)
    answer = (divisors * B) // 2
    return answer % MOD

# Read from stdin
A, B = map(int, input().split())

# Print the answer
print(solve(A, B))

Submission Info

Judge Result