C#で Project Euler P5

問題

2520 は 1 から 10 の数字の全ての整数で割り切れる数字であり, そのような数字の中では最小の値である.
では, 1 から 20 までの整数全てで割り切れる数字の中で最小の正の数はいくらになるか.
Problem 5 - PukiWiki

解答

P5.cs

using System;

public static class P5
{
    [STAThread]
    public static void Main()
    {
        Console.WriteLine(Calc());
    }
    
    private static ulong Calc()
    {
        ulong res = 1;
        for(ulong num = 1; num <= 20; num++)
        {
            res = res * num / MyMath.EuclideanAlgorithem(res, num);
        }
        return res;
    }
}

MyMath

public static class MyMath
{
    // O(log n)
    public static ulong ModPow(ulong n, ulong p, ulong m)
    {
        ulong res = 1;
        for(; p > 0; p >>= 1)
        {
            res = (p & 1) == 1 ? res * n % m : res;
            n = (n * n) % m;
        }
        return res;
    }
    // O(log n)
    public static ulong EuclideanAlgorithem(ulong a, ulong b)
    {
        ulong work;
        while(b != 0)
        {
            work = b;
            b = a % b;
            a = work;
        }
        return a;
    }
}

計算量　$O(n\log n)$
最大公約数から最小公倍数を求めていって掛け合わせるだけ。