codeforces-scrape

Codeforces scraped problems and editorials
git clone git://git.laack.co/codeforces-scrape.git
Log | Files | Refs | README

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$.