TopCoder SRM 591: PyramidSequences
public class PyramidSequences { static public long Gcd(long s, long t) { return t != 0 ? Gcd(t, s % t) : s; } public long distinctPairs(long N, long M) { long gcd = Gcd(N - 1, M - 1); long ans = 0; long x = (N - 1) / gcd; long y = (M - 1) / gcd; ans += ((x + 1) * (y + 1) + 1) / 2; ans += (gcd - 1) * x * y; return ans; } }