| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 (추가 시간 없음) | 1024 MB | 15 | 6 | 6 | 85.714% |
For any positive integer $n$, let's define Möbius function $\mu(n)$. It has values in $\{-1, 0, 1\}$ depending on the factorization of $n$ into prime factors:
For example, $\mu(1) = 1, \mu(2) = -1, \mu(6) = 1, \mu(12) = 0$.
You are given two arrays $a$ and $b$, consisting of positive integers.
Let $k_y$ be the number of pairs $(i, j), 1 \le i \le n, 1 \le j \le m$ such that $\mu(a_i\cdot b_j)$ is equal to $y$.
Your task is to calculate $k_{-1}$, $k_{0}$ and $k_1$.
The first line of input contains two integers $n, m$ ($1 \le n, m \le 2 \cdot 10^5$) --- the sizes of arrays $a$ and $b$.
The second line contains $n$ integers $a_i$ ($1 \le a_i \le 10^6$) separated by spaces.
The third line contains $m$ integers $b_i$ ($1 \le b_i \le 10^6$) separated by spaces.
Output three integers $k_{-1}, k_{0}, k_{1}$ separated by spaces in a single line, where $k_y = |\{(i, j) : \mu(a_i \cdot b_j) = y \}|$.
6 4 1 2 3 4 5 6 2 3 5 7
6 9 9