1494번: 절대값 수열

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

$O(n\lg(\min(f,s)))$

인접한 S_i와 S_i+1을 u, v라 하자.
i) u>=v*2
i가 3증가 할 때마다 u가 v*2씩 감소한다.
ii) u<v*2
u'=v
v'=abs(u-v)

연속으로 발생하는 (i)를 적절한 계산을 통해 O(1)에 모두 처리할 수 있다.
그러면 (ii)는 많아야 $O(\lg(\min(f,s)))$번 일어나므로 각 테스크를 빠르게 처리할 수 있다.

유클리디언 알고리즘의 동작 방식과 상당히 유사함을 알 수 있다.

#include<cstdio>
#include<algorithm>
using namespace std;
long long f, s, m, u, v, t;
int n;
int main() {
    for (scanf("%lld%lld%d", &f, &s, &n); n--;) {
        scanf("%lld", &m);
        u = f;
        v = s;
        while (m--) {
            swap(u, v);
            v = abs(v - u);
            t = !v || m / 3 < u / v / 2 ? m / 3 : u / v / 2;
            m -= t * 3;
            u -= t * v * 2;
        }
        printf("%lld\n", u);
    }
    return 0;
}