SRM490 Div1 Easy Starport

2015/06/21 (Sun) SRM 数学

問題

問題文

入力は正の整数 $N,M$ である． 任意の正の整数から $N$ の倍数 $kN$ を一様ランダムに選ぶ． $kN$ 以上で最小の $M$　の倍数を $lM$ とすると， $lM - kN$ の期待値はいくら？

方針

$g = \gcd(M,N), n = \frac{N}{g}, m = \frac{M}{g}$ とすると， $m$ の倍数を $n$ で割ったあまりは $n$ 未満の自然数の中から周期 $n$ で均等に現れるので， 結局それらを $g$ 倍した $0, g, 2g, \cdots , N-g$ の中から均等に現れることになる． したがって $ \frac{0+g+2g+\cdots +N-g}{N/g} = \frac{N-g}{2}$ が答え．

実装

ll gcd(ll a, ll b) {
    return std::__gcd(a,b); // at algorithm
    // return b != 0 ? gcd(b, a % b) : a;
}
ll lcm(ll a, ll b) {
    return a*gcd(a,b)/b;
}
// ax+by = gcd(a,b)
ll extgcd(ll a, ll b, ll & x, ll & y) {
    ll g = a; x = 1; y = 0;
    if (b != 0) g = extgcd(b, a % b, y, x), y -= (a / b) * x;
    return g;
}

class Starport {
public:
    double getExpectedTime(int N, int M){
        return (N-gcd(N,M))/2.0;
    }
};