P10580 [Lanqiao Cup 2024 National A] gcd and lcm

Given two numbers $x, y$, find how many different sequences $(a_1, a_2, \cdots, a_n)$ of length $n$ have the greatest common divisor of all elements equal to $x$ and the least common multiple equal to $y$. Two sequences $(a_1, a_2, \cdots, a_n)$ and $(b_1, b_2, \cdots, b_n)$ are considered different if there exists at least one position $i$ such that $a_i \neq b_i$. Since the answer may be very large, output the result modulo $998\ 244\ 353$.

The first line contains an integer $Q$, the number of queries. The next $Q$ lines each contain three integers $x, y, n$, representing one query. Adjacent integers are separated by a single space. For each query, it is guaranteed that there exists at least one sequence satisfying the conditions.

Output $Q$ lines. Each line contains one integer, the answer for each query in order.

For $40\%$ of the test cases, $n \le 30$. For $70\%$ of the test cases, $n \le 5000$. For all test cases, $1 \le Q \le 100$, $2 \le n \le 10^5$, $1 \le x, y \le 10^9$. Translated by ChatGPT 5