SRM490 Div1 Easy(250), Div2 Medium(500) Starport
N*Mの周期で繰り返すので、答えはΣi=0N-1i*M%N。NとMが互いに素ならば剰余は0〜N-1の全ての値になるので、=N(N-1)/2。
g=gcd(N,M)として、N'=N/g, M'=M/gと置くと答えは、gΣi=0N'-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; }};