BOJ 1494 : 절댓값 수열

시간복잡도

$O(L + NlogL), L = log(max(S_0, S_1))$

풀이

1번째 test case인 (21, 12)를 관찰해보자.

21, 12, 9, 3, 6, 3, 3, 0, 3, 3, 0, ...

 

보이는 것과 같이 3, 3, 0이 반복됨을 관측할 수 있다.
이로부터 같은 수가 연속해서 나오면 그 뒤는 $a, a, 0$이 반복됨을 알 수 있다.
그러나 $(10^{18}, 1)$와 같은 경우 같은 수가 연속한 경우까지 너무 오래 걸린다.
만약 $(a, b)$에서 $a \gg b$라면, $a, b, a-b, a-2b, b$까지는 자명함을 알 수 있다.
즉 $(a, b)$에서 $(a-2b, b)$, 나아가 $(a-2kb, b)$까지 확장시킬 수 있는 것이다.

 

정리해보자면, $(a, b)$에서

1. if $a=b$ : $a, a, 0, a, a, 0, ...$
2. else if $a<b$ : $(a, b)->(b, b-a)$
3. else if $b=0$ : $a, 0, a, a, 0, ...$
4. else, $(a, b) -> (a-2b, b)->...->(a-2kb, b)$ $(a \geq 2kb)$
   다음곽 같이 진행됨을 알 수 있고, 특정 쌍만 저장해두면
   꽤나 간단하게 특정 쌍과 쌍 사이의 값을 알 수 있다.

끝나는 조건은 1, 3번이고, 2번의 경우 4번 꼴로 변환된다.
(4번 꼴에서 $k=0$인 경우 $(a, b)->(b, a-b)$, 다시 반복하면 된다.)
4번의 경우 $a>b, 2kb \leq a \leq 2(k+1)b, k > 0$ 여야 하므로
$a=\alpha b$라 하면 $a = \alpha b \geq 2kb \geq 2b$이므로 $\alpha \geq 2$,
1번째 값이 절반 이하로 줆을 알 수 있다. 따라서 쌍의 수는 $O(logS_0)$이다.

코드

#include <bits/stdc++.h>  
using namespace std;  
#define ll long long  

struct z  
{  
    ll t, a, b;  
}; vector<z> q;  
vector<ll> qt;  

int N, L;  

int main()  
{  
    ll x0, x1; cin>>x0>>x1>>N;  
    q.push_back({0, x0, x1});  
    while (1)  
    {        z now = q[L];  
        if (now.a == now.b) break;  
        else if (now.a < now.b)
            q.push_back({now.t+1, now.b, now.b-now.a});  
        else if (!now.b)
            q.push_back({now.t+2, now.a, now.a});  
        else {  
            ll k = now.a / (now.b*2);  
            if (k) q.push_back({now.t + k*3,
            now.a - k*now.b*2, now.b});  
            else q.push_back({now.t+1, now.b, now.a-now.b});  
        }        
        L++;  
    }    
    for (int i = 0; i <= L; i++) qt.push_back(q[i].t);  
    while (N--) {  
        ll T; cin>>T;  
        if (T >= q[L].t)
            cout<<((T-q[L].t)%3 == 2 ? 0 : q[L].a)<<"\n";  
        else {  
            int p =
            upper_bound(qt.begin(), qt.end(), T) - qt.begin()-1;  
            if (q[p].t == T) cout<<q[p].a<<"\n";  
            else if (q[p].t + 1 == T) cout<<q[p].b<<"\n";  
            else if ((T-q[p].t)%3 == 0)
                cout<<(q[p].a - q[p].b*2*((T-q[p].t)/3))<<"\n";  
            else if ((T-q[p].t)%3 == 1) cout<<q[p].b<<"\n";  
            else cout<<(q[p].a
            - q[p].b*2*((T-q[p].t)/3) - q[p].b)<<"\n";  
        }    
    } 
    return 0;  
}