SRM 490 div1 easy:Starport
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; } }