AtCoder Beginner Contest 133 C - Remainder Minimization 2019

初の緑パフォ出せてうれしくなっている、ねむーです。

今回はAtCoder(https://atcoder.jp/contests/abc133/tasks/abc133_c)にて開催されました、AtCoder Beginner Contest 133 C問題「C - Remainder Minimization 2019」の問題と僕との戦闘記です。

0.はじめに

今回も、プログラミング言語はC#を使用しています。

1.問題文

非負整数 L , R が与えられます。 2 つの整数 i , j を L ≤ i < j ≤ R を満たすように選びます。 ( i × j ) mod 2019 の最小値を求めてください。

2.制約

• 入力は全て整数
• 0 ≤ L < R ≤ 2 × 10 9

3.入力例

• 入力

2020 2040

• 出力

2

4.初見の感想

• (i*j)%2019すればよいのは思いつく
• 全探索すると計算時間が死ぬ

5.学びポイント

• 剰余は最大2018までしかない

→数字の取りうる幅は0~2018の間、ループも最初から2019番目以降は計算する価値がない

• 計算は(i%2019)*(j%2019)でよい

→合同式の性質より、コンテスト中にGoogleで調べました（笑）

6.コードと簡単な解説

using System;
using System.Collections.Generic;
using System.Linq;

class Program
{
    static void Main(string[] args)
    {
        var input = Console.ReadLine().Split();
        long L = long.Parse(input[0]);
        long R = long.Parse(input[1]);
        long ans = long.MaxValue;
        //2019番目以降をMin条件でカット
        for(long i=L;i<=Math.Min(R,L+2018); i++)
        {
            for(long j = i + 1; j <= Math.Min(R, L + 2018); j++)
            {
　　　　 //最小値更新
                ans=Math.Min(ans,(i%2019)*(j%2019)%2019);
            }
        }
        Console.WriteLine(ans);
    }
}

7.最後に

めっちゃタイプミスしてこの問題3回出しなおしました（笑）