SRM 162 DIV2 Level One - 最小公倍数

C++ではあんまり解きたくない問題。

4,5,6とか範囲が与えられるので、最小公倍数を求める。

#include <vector>
using namespace std;

class LCMRange
{
public:
    static int lcm(int first, int last)
    {
        vector<int> numbers;
        int acc = 1;

        for (int i = first; i <= last; i++)
            numbers.push_back(i);

        for (int i = 0; i < numbers.size(); i++) {
            for(int j = i + 1; j < numbers.size(); j++)
                if (numbers[j] % numbers[i] == 0)
                    numbers[j] /= numbers[i];
            acc *= numbers[i];
        }

        return acc;
    }
};

全然イメージが広がらない。

今後使いそうなのでgcdとlcmを作ってみた。

int gcd(int a,int b) { return (b == 0) ? a : gcd(b, a % b); }

int global_lcm(int a, int b) { return a * b / gcd(a, b); }

class LCMRange
{
public:
    static int lcm(int first, int last)
    {
        int acc = 1;

        for (int i = first; i <= last; i++)
            acc = global_lcm(i, acc);

        return acc;
    }
};

おっかしいな、lcm使うとスタックオーバフローするんだよ。と思ったら、LCMRange::lcmでlcm使ってる！！

再帰しまくってた（汗