| 시간 제한 | 메모리 제한 | 제출 | 정답 | 맞힌 사람 | 정답 비율 |
|---|---|---|---|---|---|
| 2 초 | 1024 MB | 530 | 238 | 195 | 49.367% |
피돌이는 문득 피갤이 길이가 $N$인 정수열 $A$였다는 사실을 깨달았다. 이 사실이 마음에 들지 않았던 피돌이는 피갤에 여러 개의 폭탄을 던질 계획을 세웠다. 피돌이의 이 사악한 계획을 알게 된 피붕이는 계획을 막기는 귀찮으니 대신 모든 계획이 수행된 이후 피갤의 피해 정도를 예측하고자 한다.
피돌이의 계획은 다음과 같은 행동을 $M$번 수행하는 것이다.
이때, 폭탄을 맞은 각 원소는 폭발에 휘말려 즉시 자신의 서로 다른 소인수들 중 하나의 값으로 변하게 된다. 또한, 각 소인수로 변할 확률은 균일하다.
예측마저도 귀찮아진 피붕이를 대신해, 계획된 모든 폭발이 일어난 후 $\sum\limits_{i=1}^{N} A_i$의 기댓값을 구해보자!
첫째 줄에 수열의 길이 $N$과 계획의 수 $M$이 공백으로 구분되어 주어진다. ($1 \le N \le 200\,000, 0 \le M \le 200\,000$)
둘째 줄에 $A_1, A_2, \dots, A_N$이 공백으로 구분되어 주어진다. ($2 \le A_i \le 500\,000$, $A_i$는 정수)
셋째 줄부터 $M$개의 줄에 걸쳐 피돌이의 계획 $i, j$가 공백으로 구분되어 주어진다. ($1 \le i \le j \le N$)
첫째 줄에 모든 폭발이 적용된 이후 수열의 모든 원소의 합의 기댓값을 출력한다.
출력한 값과 정답의 상대/절대 오차가 $10^{-9}$ 이하라면 정답으로 인정된다.
| 번호 | 배점 | 제한 |
|---|---|---|
| 1 | 4 | $M = 0$ |
| 2 | 20 | 각 계획은 서로 교차하지 않는다. |
| 3 | 76 | 추가적인 제약 조건이 없다. |
1 1 12 1 1
2.5
값이 12인 원소에 폭발이 일어난다면, $12$의 서로 다른 소인수는 $2$와 $3$이므로, 이 원소는 폭발 이후 $\frac{1}{2}$의 확률로 $2$로, $\frac{1}{2}$의 확률로 $3$으로 변한다. 따라서, 기댓값은 $\frac{1}{2} \times 2 + \frac{1}{2} \times 3 = \frac{5}{2}$가 된다.
10 4 30 155 21 59 30 13 2 6 10 98 1 2 8 10 2 5 3 6
114.166666666667
소인수란 어떤 수의 약수 중에서, 소수인 것을 말한다.
Contest > BOJ User Contest > 피갤컵 > 제3회 피갤컵 C번