Battling with Numbers
Contest: COMPFEST 15 - Preliminary Online Mirror (Unrated, ICPC Rules, Teams Preferred)
Difficulty rating: 1400
Tags: combinatorics, math, number theory

On the trip to campus during the mid semester exam period, Chaneka thinks of two positive integers $$$X$$$ and $$$Y$$$. Since the two integers can be very big, both are represented using their prime factorisations, such that:

- $$$X=A_1^{B_1}\times A_2^{B_2}\times\ldots\times A_N^{B_N}$$$ (each $$$A_i$$$ is prime, each $$$B_i$$$ is positive, and $$$A_1<A_2<\ldots<A_N$$$)
- $$$Y=C_1^{D_1}\times C_2^{D_2}\times\ldots\times C_M^{D_M}$$$ (each $$$C_j$$$ is prime, each $$$D_j$$$ is positive, and $$$C_1<C_2<\ldots<C_M$$$)

Chaneka ponders about these two integers for too long throughout the trip, so Chaneka's friend commands her "Gece, deh!" (move fast) in order to not be late for the exam.

Because of that command, Chaneka comes up with a problem, how many pairs of positive integers $$$p$$$ and $$$q$$$ such that $$$\text{LCM}(p, q) = X$$$ and $$$\text{GCD}(p, q) = Y$$$. Since the answer can be very big, output the answer modulo $$$998\,244\,353$$$.

Notes:

- $$$\text{LCM}(p, q)$$$ is the smallest positive integer that is simultaneously divisible by $$$p$$$ and $$$q$$$.
- $$$\text{GCD}(p, q)$$$ is the biggest positive integer that simultaneously divides $$$p$$$ and $$$q$$$.

Input format:
The first line contains a single integer $$$N$$$ ($$$1 \leq N \leq 10^5$$$) — the number of distinct primes in the prime factorisation of $$$X$$$.

The second line contains $$$N$$$ integers $$$A_1, A_2, A_3, \ldots, A_N$$$ ($$$2 \leq A_1 < A_2 < \ldots < A_N \leq 2 \cdot 10^6$$$; each $$$A_i$$$ is prime) — the primes in the prime factorisation of $$$X$$$.

The third line contains $$$N$$$ integers $$$B_1, B_2, B_3, \ldots, B_N$$$ ($$$1 \leq B_i \leq 10^5$$$) — the exponents in the prime factorisation of $$$X$$$.

The fourth line contains a single integer $$$M$$$ ($$$1 \leq M \leq 10^5$$$) — the number of distinct primes in the prime factorisation of $$$Y$$$.

The fifth line contains $$$M$$$ integers $$$C_1, C_2, C_3, \ldots, C_M$$$ ($$$2 \leq C_1 < C_2 < \ldots < C_M \leq 2 \cdot 10^6$$$; each $$$C_j$$$ is prime) — the primes in the prime factorisation of $$$Y$$$.

The sixth line contains $$$M$$$ integers $$$D_1, D_2, D_3, \ldots, D_M$$$ ($$$1 \leq D_j \leq 10^5$$$) — the exponents in the prime factorisation of $$$Y$$$.

Output format:
An integer representing the number of pairs of positive integers $$$p$$$ and $$$q$$$ such that $$$\text{LCM}(p, q) = X$$$ and $$$\text{GCD}(p, q) = Y$$$, modulo $$$998\,244\,353$$$.

Constraints:
Time limit: 1.0 s
Memory limit: 256.0 MB

Note:
In the first example, the integers are as follows:

- $$$X=2^2\times3^1\times5^1\times7^2=2940$$$
- $$$Y=3^1\times7^1=21$$$

The following are all possible pairs of $$$p$$$ and $$$q$$$:

- $$$p=21$$$, $$$q=2940$$$
- $$$p=84$$$, $$$q=735$$$
- $$$p=105$$$, $$$q=588$$$
- $$$p=147$$$, $$$q=420$$$
- $$$p=420$$$, $$$q=147$$$
- $$$p=588$$$, $$$q=105$$$
- $$$p=735$$$, $$$q=84$$$
- $$$p=2940$$$, $$$q=21$$$

In the third example, the integers are as follows:

- $$$X=2^1\times5^1=10$$$
- $$$Y=2^1\times3^1=6$$$

There is no pair $$$p$$$ and $$$q$$$ that simultaneously satisfies $$$\text{LCM}(p,q)=10$$$ and $$$\text{GCD}(p,q)=6$$$.

Example input:
4
2 3 5 7
2 1 1 2
2
3 7
1 1

Example output:
8

Example input:
2
1299721 1999993
100000 265
2
1299721 1999993
100000 265

Example output:
1

Editorial:
For a prime $$$k$$$, let $$$f_k(w)$$$ be the exponent of $$$k$$$ in the factorisation of $$$w$$$. In particular, if the factorisation of $$$w$$$ does not contain $$$k$$$, then $$$f_k(w)=0$$$.
We can obtain that for any prime $$$k$$$, it holds that:
• $$$f_k(X)=f_k(\text{LCM}(p,q))=\max(f_k(p),f_k(q))$$$
• $$$f_k(Y)=f_k(\text{GCD}(p,q))=\min(f_k(p),f_k(q))$$$
For each prime $$$k$$$, there are three cases:
• If $$$f_k(X)<f_k(Y)$$$, then it is impossible to assign the exponents since $$$\max(f_k(p),f_k(q))<\min(f_k(p),f_k(q))$$$ cannot be satsified.
• If $$$f_k(X)=f_k(Y)$$$, then there is only one way to assign the exponents, which is $$$f_k(p)=f_k(q)=f_k(X)$$$.
• If $$$f_k(X)>f_k(Y)$$$, then there are two ways to assign the exponents, which are the following:   $$$f_k(p)=f_k(X)$$$, $$$f_k(q)=f_k(Y)$$$  $$$f_k(p)=f_k(Y)$$$, $$$f_k(q)=f_k(X)$$$
• $$$f_k(p)=f_k(X)$$$, $$$f_k(q)=f_k(Y)$$$
• $$$f_k(p)=f_k(Y)$$$, $$$f_k(q)=f_k(X)$$$
This means, if there is at least one prime $$$k$$$ such that $$$f_k(X)<f_k(Y)$$$, the answer is $$$0$$$. Otherwise, the answer is $$$2$$$ to the power of the number of primes $$$k$$$ such that $$$f_k(X)>f_k(Y)$$$.
To maintain the values of $$$f_k(X)$$$ and $$$f_k(Y)$$$, you can use two pointers, the map data structure, or other methods.
Time complexity: $$$O(N)$$$