Particle

競技プログラミングについての雑記

SRM 591 Div1 Med PyramidSequences

editorial にわかりやすく解法が纏まっているが、良問なので(できるだけ)自力で解く方が良さそう。
https://apps.topcoder.com/wiki/display/tc/SRM+591

一応ヒントを出すと、整数のペアなので、それに対する典型手法を用いると見通しが良くなります。(editorial の 2 行目にその手法が書いてあります。)

class PyramidSequences {
	public:
	long long distinctPairs(ll N, ll M) {
		ll n2 = N-1, m2 = M-1;
		ll g = __gcd(n2, m2);
		ll n3 = n2/g, m3 = m2/g;
		ll d = (n3-1)*(m3-1)/2;
		return n2*m2/g-d+1;
	}
};