1866B.md (3223B)
1 Source: https://codeforces.com/problemset/problem/1866/B 2 3 B. Battling with Numbers 4 5 time limit per test 6 7 1 second 8 9 memory limit per test 10 11 256 megabytes 12 13 input 14 15 standard input 16 17 output 18 19 standard output 20 21 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: 22 23 * $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 \lt A_2 \lt \ldots \lt A_N$) 24 * $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 \lt C_2 \lt \ldots \lt C_M$) 25 26 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. 27 28 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$. 29 30 Notes: 31 32 * $\text{LCM}(p, q)$ is the smallest positive integer that is simultaneously divisible by $p$ and $q$. 33 * $\text{GCD}(p, q)$ is the biggest positive integer that simultaneously divides $p$ and $q$. 34 35 Input 36 37 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$. 38 39 The second line contains $N$ integers $A_1, A_2, A_3, \ldots, A_N$ ($2 \leq A_1 \lt A_2 \lt \ldots \lt A_N \leq 2 \cdot 10^6$; each $A_i$ is prime) — the primes in the prime factorisation of $X$. 40 41 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$. 42 43 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$. 44 45 The fifth line contains $M$ integers $C_1, C_2, C_3, \ldots, C_M$ ($2 \leq C_1 \lt C_2 \lt \ldots \lt C_M \leq 2 \cdot 10^6$; each $C_j$ is prime) — the primes in the prime factorisation of $Y$. 46 47 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$. 48 49 Output 50 51 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$. 52 53 Examples 54 55 Input 56 57 ``` 58 4 59 2 3 5 7 60 2 1 1 2 61 2 62 3 7 63 1 1 64 ``` 65 66 Output 67 68 ``` 69 8 70 ``` 71 72 Input 73 74 ``` 75 2 76 1299721 1999993 77 100000 265 78 2 79 1299721 1999993 80 100000 265 81 ``` 82 83 Output 84 85 ``` 86 1 87 ``` 88 89 Input 90 91 ``` 92 2 93 2 5 94 1 1 95 2 96 2 3 97 1 1 98 ``` 99 100 Output 101 102 ``` 103 0 104 ``` 105 106 Note 107 108 In the first example, the integers are as follows: 109 110 * $X=2^2\times3^1\times5^1\times7^2=2940$ 111 * $Y=3^1\times7^1=21$ 112 113 The following are all possible pairs of $p$ and $q$: 114 115 * $p=21$, $q=2940$ 116 * $p=84$, $q=735$ 117 * $p=105$, $q=588$ 118 * $p=147$, $q=420$ 119 * $p=420$, $q=147$ 120 * $p=588$, $q=105$ 121 * $p=735$, $q=84$ 122 * $p=2940$, $q=21$ 123 124 In the third example, the integers are as follows: 125 126 * $X=2^1\times5^1=10$ 127 * $Y=2^1\times3^1=6$ 128 129 There is no pair $p$ and $q$ that simultaneously satisfies $\text{LCM}(p,q)=10$ and $\text{GCD}(p,q)=6$.