TCHS08 Online Round 3 Medium 練習

問題

1〜nまでの全ての数で割り切れる最小の数を987654321で割った余りを求めなさい。

解

これもやっていくだけ。最小公倍数なので素数をチェックしてかけていく。

注意しなきゃいけないのは、ある素数 p (1 ≦ p ≦ n) に対して、p^x (p^x ≦ n) が最大になるような p^x を使うというところ。

たとえば n = 10 のとき、素数としては 2, 3, 5, 7だけど実際乗算するのは 8(2³), 9(3²), 5, 7 にする。

using System;
using System.Text;
using System.Text.RegularExpressions;
using System.Collections;
using System.Collections.Generic;

public class OneTwoThree {
    private bool isp(int a)
    {
        if (a <= 2) return true;
        if (a % 2 == 0) return false;
        for (int i = 3; i * i <= a; ++i)
            if (a % i == 0)
                return false;
        return true;
    }

    public int minimalNumber(int n) {
        long t = 1;

        for (int i = 2; i <= n; ++i)
        {
            if (isp(i))
            {
                long p = i;
                while (p * i <= n) p *= i;
                t *= p;
                t %= 987654321;
            }
        }

        return (int)t;
    }
}

EasyよりMediumのソースの方が短くて纏まってる。やるだけ問題苦手。