Lesson 10: ChocolatesByNumbers (Chocolates By Numbers)

Lesson 10:  ChocolatesByNumbers
https://codility.com/programmers/lessons/10

これは簡単ですね。

チョコレートを食べるのをやめるときは、同じ場所にたどり着いた時です。これは、NとM最小公倍数にの距離に達した時です。その距離をMで割れば食べれたチョコの数がわかりますね。

ここで
NとMの最小公倍数     = (N * M) / gcd(N, M) ですから
NとMの最小公倍数 / M = (N * M) / gcd(N, M) / M = N / gcd(N, M)となります。

なぜ最小公倍数になるかイメージがつかめない人は下の図を見てください。                  

位置 　　　　(N = 7): 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0 1 2 3 4 5 6 0
食べるチョコ (M = 4): X       X       X       X       X       X       X       X

これで１００％のスコアがもらえました。 

//we expect the compiler will perform the tail call optimazation.
int gcd(int a, int b, int res)
{
    if (a == b){
        return res * a;
    }
    if (a % 2 == 0 && b % 2 == 0){
        return gcd(a >> 1, b >> 1, 2 * res);
    }
    if (a % 2 == 0){
        return gcd(a >> 1, b, res);
    }
    if (b % 2 == 0){
        return gcd(a, b >> 1, res);
    }
    if (a > b){
        return gcd(a - b, b, res);
    }
    
    return gcd(a, b - a, res);    
}
int solution(int N, int M) 
{
    int denominator   = gcd(N, M, 1);
    int numerator     = N;
    
    return (numerator / denominator);
}