C++

[c++] 백준 14476 (최대공약수 하나빼기, 누적합, 최대공약수, 유클리드 호제법)

최대공약수를 구하는 함수는 수는 유클리드 호제법을 이용하여 정의할 수 있다. gcd(36, 8) => gcd(8, 36%8) ....gcd(36,8) => gcd(8,4) => gcd(4,0) => 최대공약수는 4가 된다. int gcd(int a, int b){ while(b != 0){ int r = a % b; a = b; b = r; } return b; } 이를 활용하여 누적합을 적용해 본다. number 8 12 24 36 48 L to R 8 4 4 4 4 R to L 4 12 12 12 48 각 L to R과 R to L을 구한 이유는 k수를 제외하고 최대공약수를 구할때 O(n) 시간복잡도로 구하기 위해서이다. 즉, k=8 , 최대공약수 = RL[1] k=12, 최대공약수 = gcd(LR[..