SRM 490 div1 easy:Starport - mayoko’s diary

SRM練習会に参加。easyだけ通しました。一応チェックしていたとはいえ,easyもちょっとあぶなかったですね(整数演算が高速だから最悪ケースでも間に合ったけどすごい勢いでchallengeされるコードを書いてしまった)。

問題

解法

NとMの最大公約数を考える(gとする)。
a*N + b*M = g
の解は保証されており,またgより小さい値xについては
a*N + b*M = x
の解は存在しないことが知られている(拡張ユークリッドの互除法)。
これらのことより,待つ時間としてgの倍数のみがあり得,またN未満のgの倍数すべてが現れることがわかる。また,それぞれの数が現れる頻度を考えると,
g*0, g*1, ..., N-g
はそれぞれ同じ頻度ででなければおかしい(mod Nを考えることになるので周期的に待つ時間が現れ,またgの倍数はすべて出現するはずなので)。
よって,単純にN未満のgの倍数の和を取ってその個数で割れば良い。本番は和の公式を使わないで素直にfor文を回して答えを求めるというアホプレイをかました。
以下ソースコード

class Starport {
public:
    double getExpectedTime(int N, int M) {
        ll n = N, m = M;
        ll g = __gcd(n, m);
        ll num = n/g;
        ll sum = (num-1)*num/2 * g;
        return (1. * sum) / num;
    }
}