[BOJ] 9537번: Magical GCD

https://www.acmicpc.net/problem/9537

수열에서의 GCD는 매우 중요한 성질이 있는데, 값의 변화가 많아봐야 log2(MAX)만큼 일어난다는 것입니다. 예를 들어 문제의 예시인 30 60 20 20 20의 경우, (30) -> 30, (30 60) -> 30, (30 60 20) -> 10, ... 을 볼 때 값의 변화가 한 번 일어났습니다. 왜냐하면 값이 변할 때 적어도 2로 나누어져야하기 때문입니다. 같은 값이 여럿 있을 때에는 가장 길이가 길게 하는, 즉 제일 왼쪽의 것만 계속 들고가면 됩니다. 이제 진행하면서 값이 변화하는 지점만 들고가면, $O(Nlg(10^12))$에 해결이 가능합니다.

예를 들어 30 60 20 20 20의 경우,

30을 보고난 후 (30, 0)

60을 보고난 후(30, 0), (60, 1)

20을 보고난 후(10, 0), (20, 2)

20을 보고난 후(10, 0), (20, 2)

20을 보고난 후(10, 0), (20, 2)

을 들고갑니다. 저는 그냥 vector를 N개 잡아 해결했는데 map을 가지고 해결한 코드도 볼 수 있었습니다.

https://github.com/blisstoner/BOJ/blob/master/9537.cpp