movie_jo   9년 전

간략하게 방식을 설명하자면

a[i]는 i번째 수를 저장하는거고

그냥 n^2으로 하면 시간초과가 날 것 같아서

g[ i ][ j ]와 n[ i ][ j ]는

g[ i ][ j ]를 공통 gcd로 하는 숫자가 n[ i ][ j ]개 있다

입니다.

그래서 2개를 번갈아 돌면서

처음에는 모든 (1~2), (2~3), ... , (n-1~n)의 pair가 g[ 1 ][ j ]에 넣은 상태로 시작하구요

이걸 길이 (l[ i ])가 1이 될 때 까지 하고

할 때 마다 max값을 체크해서 마지막에 max값을 출력하는 구조인데요

1) 1개만 있을 때 최대를 0으로 고려 -> 틀림

2) 1개만 있을 때 최대를 그 숫자로 고려 -> 틀림

3) 1)에서 long long으로 수정 -> 틀림

4) 2)에서 long long으로 수정 -> 틀림

시간초과면 알고리즘이 잘못됬거니 하겠는데 다 틀려버리니 논리에 오류가 있는데 도통 모르겠네요 ㅠㅠ

hahaha   9년 전

일단 a배열도 롱롱으로 받아야합니다

h0ngjun7   9년 전

어떻게 푸신 지 잘 이해가 되지 않지만... 음...

개인적으로 생각했을 때, 이 문제의 핵심은 어떤 구간 [a, b](1<=a<=b<=n)에 속하는 원소들 x(i)(a<=i<=b)의 gcd를 누적(?.. 그 결과에 또 gcd를 하고, 또 gcd를 하고를 반복..)하다보면, gcd가 바뀌는 횟수가 log(n)을 넘지 않는다는 것입니다. 크기가 최소인 지수가 2인데, x(i)<=10^12이므로 2^40 > 10^12인 걸 고려하면 그 리스트(40개 미만)들을 들고다니면서 처리할 수 있다는 것을 알 수 있죠.

h0ngjun7   9년 전

저희 팀원 중 한 명은 LCA 알고리즘을 수행할 때처럼 i번째부터 i + 2^k번째 원소 사이의 gcd를 전처리로 다 구한 후, 매 i에 대해서 현재 gcd값이 계속 누적하여도 같은 끝 인덱스 j를 찾고,  그 다음부터의 gcd로 또 다른 j'을 찾고.... 이런 식의 풀이를 떠올렸더라구요. 이 알고리즘은 O(n log^2 n)인 것 같습니다.

댓글을 작성하려면 로그인해야 합니다.