TopCoder SRM 369 Div1 Medium AbsSequence

問題

次のように定義される数列aがある。
a[0] = first
a[1] = second
a[i] = | a[i - 1] - a[i - 2] | (i > 1)
このとき、aのx番目の要素を求めよ。

制約条件

first, second≦10^18
x≦10^18

方針

aを実際に最初のいくつかの項を出力してみると、
長さ3の周期で規則的になっていることがわかる。

a[i] = a[i - 3]で、
a[i - 1] = a[i - 4] - d
みたいになっていて、a[i - 1]が0未満になるところで、
数字だけ変わってまた同じ規則が現れる。

なので、a[i] = a[i - 3]が出てきたところで、
適当に繰り返し部分を圧縮してやる。
すると、gcdの計算みたいになって、O(log max{x, first, second})くらいの計算量でa[x]が求まる。

ソースコード

map<ll, ll> m;
ll solve(ll x){
	
	for(ll i = 2; i <= x; i++){
		ll nxt = abs(m[i - 1] - m[i - 2]);
		if(i < 4 || !m.count(i - 3) || m[i - 3] != nxt){
			m[i] = nxt;
			continue;
		}
		ll d = m[i - 4] - m[i - 1];
		ll loop = (x - i) / 3;
		if(d < 0) loop = 0;
		else if(d) loop = min(loop, m[i - 1] / d);
		
		m[i + loop * 3] = nxt;
		m[i + loop * 3 - 1] = m[i - 1] - d * loop;
		i += loop * 3;
	}
	return m[x];
}

class AbsSequence {
	public:
	vector <string> getElements(string first, string second, vector <string> indices) 
	{
		m.clear();
		m[0] = atoll(first.c_str());
		m[1] = atoll(second.c_str());
		
		vector<string> ans;
		rep(i, indices.size()){
			char buf[100];
			sprintf(buf, "%lld", solve(atoll(indices[i].c_str())));
			ans.pb(buf);
		}
		return ans;
	}
};