S5. Math Homework
레이팅 미적용의견: 0
Your math teacher has given you an assignment involving coming up with a
sequence of \(N\) integers \(A_1,\ldots, A_N\), such that \(1 \le A_i \le 1\ 000\ 000\ 000\) for each
\(i\).
The sequence \(A\) must also satisfy
\(M\) requirements, with the \(i\)th one stating that the GCD
(Greatest Common Divisor) of the contiguous subsequence \(A_{X_i}, \ldots, A_{Y_i}\) \((1 \le X_i \le Y_i \le N)\) must be equal to
\(Z_i\). Note that the GCD of a
sequence of integers is the largest integer \(d\) such that all the numbers in the
sequence are divisible by \(d\).
Find any valid sequence \(A\) consistent with all of these
requirements, or determine that no such sequence exists.
\(1 \le A_i \le 1\ 000\ 000\ 000\)
\((1 \le X_i \le Y_i \le N)\)
\((1 \le i \le M)\)
Marks
The following table shows how the available 15 marks are
distributed.
| 3 marks | \(1 \leq N \le 2000\) | \(1 \le M \leq 2000\) | \(1 \le Z_i \le 2\) for each \(i\) |
|---|---|---|---|
| 4 marks | \(1 \leq N \le 2000\) | \(1 \le M \leq 2000\) | \(1 \le Z_i \le 16\) for each \(i\) |
| 8 marks | \(1 \le N \leq 150\,000\) | \(1 \le M \leq 150\,000\) | \(1 \le Z_i \le 16\) for each \(i\) |
The first line contains two space-separated integers, \(N\) and \(M\).
The next \(M\) lines each contain three
space-separated integers, \(X_i\),
\(Y_i\), and \(Z_i\) \((1 \le i \le M)\).
If no such sequence exists, output the string
Impossible on one line. Otherwise, on one
line, output \(N\) space-separated
integers, forming the sequence \(A_1,\ldots,A_N\). If there are multiple
possible valid sequences, any valid sequence will be
accepted.
2 2
1 2 2
2 2 64 6If \(A_1 =4\) and \(A_2 = 6\), the GCD of \([A_{1}, A_2]\) is \(2\) and the GCD of \([A_2]\) is \(6\), as required. Please note that
other outputs would also be accepted.
2 2
1 2 2
2 2 5ImpossibleThere exists no sequence \([A_1,A_2]\)
such that the GCD of \([A_1,A_2]\) is
\(2\) and the GCD of \([A_2]\) is \(5\).
평가 및 의견
S5. Math Homework
Log in to rate problems.
아직 의견이 없습니다. 자격이 된다면 위 양식에서 가장 먼저 평가해 보세요.
풀이 제출
S5. Math Homework