[일반] 1C 풀이 설명'해줘'

즈티(heeda0528) 2021-10-31 01:52 추천 0

x에도 나눠지고 y에도 나눠지면 xy에도 나눠짐

익명(112.187) 2021-10-31 01:57
답글
a_i에 대해 2 to i+1까지 모든 수 lcm에 나눠지는지 체크

익명(112.187) 2021-10-31 01:58
답글
아 1이구나 ㅈㅅ

익명(112.187) 2021-10-31 01:59
1. 구간 하나에 대해 생각해보면, 뒤에서부터 보면서 그리디하게 분해해주면 됨 2. 이제 이걸 모든 구간으로 확장시키면, 뒤에서부터 보면서 i번째 인덱스까지 쪼갰을때 모든 가능한 첫원소의 값(+ 그러한 구간의 개수, 가중치 등)을 관리하면 됨 3. 시복은 O(n루트x)임, x는 10만 / 이유는 가능한 첫 원소의 값이 O(루트ai)이기 때문

익명(223.62) 2021-10-31 02:00
답글
이유는 [x/i](i는 정수)의 가능한 값의 개수에 대해 생각해보면됨

익명(223.62) 2021-10-31 02:01
답글
와... 구간 여러개를 어떻게 관리하나 했는데 이게 되네.. ㄳㄳ

즈티(heeda0528) 2021-10-31 02:13
각 원소를 분할할 때 끝값이 될 수 있는 서로 다른 수는 O(sqrt(N))개라서 모든 상태에 대한 dp를 O(Nsqrt(N))에 계산해 줄 수 있음

익명(223.39) 2021-10-31 02:01
답글
sqrt(N)이 아니라 sqrt(10^5)ㅋㅋㅋ

익명(223.39) 2021-10-31 02:02

댓글 8