1000000007系: 合同

この問題

B - Training Camp

まっっったくわかりませんでした。
さすがに普通に1*1,1*2,2*3,6*4,24*5....x*nをしたらダメなんだろうなと思ったのですが
解説をみようが数学の知識が欠陥しすぎて全くわかりませんでした。
JavaのLongだとMAXは9223372036854775807なのでループ20回目以降からマイナスの値がでてきて途中から0になりますw
いわゆるオーバーフローが発生します。
平たくいうとオーバーフローを発生させないように問題を解け、ということです

問題を解くための前提知識

まずはコードに落とし込むより以前に数学の基礎知識の勉強からです。
まず合同ってなにそれおいしいの？ってところからです

• mod 3の場合 (modは剰余のことを指す)
  5 ≡ 8 というのが成り立つらしいです。剰余において二つの数字は等しいという意味らしい。

もう数学的なところはこの記事が大変わかりやすかったです。
tsujimotter.hatenablog.com

「掛け算した結果のあまりは、もとの数のあまり同士を掛け算した結果に合同である」ということです。これが「あまりの世界」における重要な性質です。

いや、こんなん知らん知らん.... でも検証したら本当だった..... こう考えると、合同式の積の意味がようやくわかるような... mathtrain.jp

a≡b,c≡d のとき，ac≡bd が成立します。つまり，合同式は辺々かけ算できます。 特に，ac≡bc です。

記事には、

3⁴ = 81 (mod 19) = 19 * 4 + 5
よって、3⁴ ≡ 5
3⁵ = 243 (mod 19) = 19 * 12 + 15
よって、3⁵ ≡ 15
すなわち、3⁵ ≡ 5*3 となると記述してあります。

（5*3の3は、3のn乗するからの意味の3）
これでac≡bdとなることがなんとなく理解できました。

ようやく本題

ここまできて、ようやくコードに落とし込める前提知識が揃ったことになりますw
上記での検証からわかることは、 n*1 % x を行なった場合の解(yとする)に y*2 % x, y*3%x...をしていけばいいということです
コードにすると少しわかりやすい? というか行数は全くいりません

import java.util.Scanner;

public class Main99 {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);

        long n = sc.nextLong();
        sc.close();

        int mod = 1000000007;
        long p = 1;
        
        for(long i=1; i<=n; i++) {
            p = p * i % mod;
        }
        System.out.println(p);
    }
}

こうすることで、対応したい値の積を求めてmodした値をさらに積算できます。 結果として、順々に掛け合わせずに、（オーバーフローせずに）解を求めることができます。