시간 제한메모리 제한제출정답맞힌 사람정답 비율
2 초 1024 MB53023819549.367%

문제

피돌이는 문득 피갤이 길이가 $N$인 정수열 $A$였다는 사실을 깨달았다. 이 사실이 마음에 들지 않았던 피돌이는 피갤에 여러 개의 폭탄을 던질 계획을 세웠다. 피돌이의 이 사악한 계획을 알게 된 피붕이는 계획을 막기는 귀찮으니 대신 모든 계획이 수행된 이후 피갤의 피해 정도를 예측하고자 한다.

피돌이의 계획은 다음과 같은 행동을 $M$번 수행하는 것이다.

  • $i \ j$: $A_i, A_{i+1},\ \dots, A_j$에 폭탄을 던진다.

이때, 폭탄을 맞은 각 원소는 폭발에 휘말려 즉시 자신의 서로 다른 소인수들 중 하나의 값으로 변하게 된다. 또한, 각 소인수로 변할 확률은 균일하다.

예측마저도 귀찮아진 피붕이를 대신해, 계획된 모든 폭발이 일어난 후 $\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}$ 이하라면 정답으로 인정된다.

서브태스크

번호배점제한
14

$M = 0$

220

각 계획은 서로 교차하지 않는다.

376

추가적인 제약 조건이 없다.

예제 입력 1

1 1
12
1 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}$가 된다.

예제 입력 2

10 4
30 155 21 59 30 13 2 6 10 98
1 2
8 10
2 5
3 6

예제 출력 2

114.166666666667

노트

소인수란 어떤 수의 약수 중에서, 소수인 것을 말한다.

출처

Contest > BOJ User Contest > 피갤컵 > 제3회 피갤컵 C번

채점 및 기타 정보

  • 예제는 채점하지 않는다.