TopCoder SRM 591 Div1 Medium PyramidSequences

さてDiv1 Medium。本番には最後まで詰め切れなかった…。
http://community.topcoder.com/stat?c=problem_statement&pm=12619

問題

数Xに対して、周期2(X-1)の次の数列を考える。
{1,2,...,X-2,X-1,X,X-1,X-2,...,3,2,1,2,3...}

2つの整数N,Mに対して、それぞれ上記の数列を作ったとき、Nから生成した数列AとMから生成した数列Bに対し、A[i]とB[i]のdistinctのペアの組み合わせ数を答えよ。

解法

Editorialが非常にわかりやすい。

元の数列を1ずらして、{0,1,2,...,X-3,X-2,X-1,X-2,X-3,...,2,1,0,1,2...}として考える。
(N-1)と(M-1)の最大公約数をGとする。
Editorialを見てわかるとおり、両数列でGで割り切れる要素でかつGで割った商の偶奇が一致するものは互いにペアを構成する可能性がある。
そのような組みわせは通り。

数列AのうちGで割り切れない要素については、Gで割った余りをRとすると、数列Bのうち同様にGで割った余りがRまたは(G-R)になったもののうち半分とペアを構成する可能性がある。
そのような組み合わせは通り。
あとは足すだけ。

class PyramidSequences {
	public:
	long long distinctPairs(int N_, int M_) {
		ll N=N_, M=M_;
		ll G=__gcd(N-1,M-1);
		ll ret = (G-1) * ((N-1)/G) * ((M-1)/G) + ((1+(N-1)/G)*(1+(M-1)/G)+1)/2;
		
		return ret;
	}
};

まとめ

終わってみると非常にあっさり。
こんな簡単にかけるDiv1 Mediumって珍しいな。