SRM490 Div1 Easy(250), Div2 Medium(500) Starport

Starport

N*Mの周期で繰り返すので、答えはΣ_i=0^N-1i*M%N。NとMが互いに素ならば剰余は0〜N-1の全ての値になるので、=N(N-1)/2。
g=gcd(N,M)として、N'=N/g, M'=M/gと置くと答えは、gΣ_i=0^N'-1i*M'%N'=gN'(N'-1)/2=N(N-g)/2。

int gcd( int a, int b )
{
    if ( a == 0 )  return b;
    if ( b == 0 )  return a;
    if ( a < b )   return gcd( a, b%a );
    else           return gcd( a%b, b );
}

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