#1175958 (PyPy3) No.3485 Find 495-like Number

• 問題: No.3485 Find 495-like Number
• ユーザー: LyricalMaestro
• 提出日時: 2026-08-10 01:06:21
• 言語: PyPy3 (7.3.17)
• 結果: WA
• 実行時間: -
• コード長: 4,491 bytes
• コンパイル時間: 236 ms
• コンパイル使用メモリ: 95,724 KB
• 実行使用メモリ: 94,672 KB
• 最終ジャッジ日時: 2026-08-10 01:06:35
• 合計ジャッジ時間: 12,450 ms
• ジャッジサーバーID （参考情報）: judge2_0 / judge1_0

ファイルパターン	結果
sample	AC * 3
other	AC * 29 WA * 5

ソースコード

# https://yukicoder.me/problems/no/3485

import random
from typing import Sequence


class MillerRabin:
    """
    ミラー・ラビン素数判定法。

    確定的判定(デフォルト)と確率的判定を切り替えられる。

        mr = MillerRabin()                     # 確定的(n < 2^64)
        mr.is_prime(1000000007)                # -> True

        mr = MillerRabin(probabilistic=True)   # 確率的(上限なし)
        mr.is_prime((1 << 89) - 1)             # -> True

    probabilistic=False の場合は固定底集合により n < 2^64 を誤りなく判定する。
        この範囲を超える入力に対しては保証がないため例外を送出する。
    probabilistic=True の場合はランダムなk個の底で確率的に判定する。
        合成数を素数と誤る確率は高々 4^(-k)。上限なく任意の整数に使える。
    """

    # n の大きさごとに「その範囲の奇数合成数を必ず見破る」ことが確認されている
    # 固定底集合。(閾値, 底集合) を閾値の昇順に並べる。
    # n が閾値未満なら、その底集合で確定判定できる。小さい n ほど底が少なく速い。
    # 出典: https://drken1215.hatenablog.com/entry/2023/05/23/233000
    _DETERMINISTIC_TABLE = (
        (4759123141, (2, 7, 61)),
        (1 << 64, (2, 325, 9375, 28178, 450775, 9780504, 1795265022)),
    )

    def __init__(self, probabilistic: bool = False, k: int = 40):
        """
        probabilistic: Trueなら確率的判定、Falseなら確定的判定(デフォルト)。
        k: 確率的判定で用いる底の個数。
        """
        self.probabilistic = probabilistic
        self.k = k

    def is_prime(self, n: int) -> bool:
        """
        nが素数かどうかを判定する。
        """
        if n < 2:
            return False
        # 2, 3 は基底ケース。底集合に必ず 2 が含まれるため試し割りは不要だが、
        # 確率的判定の底選択 randrange(2, n-1) が n<4 で範囲エラーになるのを防ぐ。
        if n < 4:
            return True

        # n - 1 = 2^s * d (dは奇数)
        d = n - 1
        s = 0
        while d % 2 == 0:
            d //= 2
            s += 1

        for a in self._select_bases(n):
            if not self._witness(n, a, d, s):
                return False

        return True

    def _select_bases(self, n: int) -> Sequence[int]:
        """
        判定に用いる底の集合を返す。
        確率的判定ならランダムなk個、確定的判定ならnの大きさに応じた固定底集合。
        """
        if self.probabilistic:
            return [random.randrange(2, n - 1) for _ in range(self.k)]

        if n >= 1 << 64:
            raise ValueError(
                "確定的判定は n < 2^64 のみ対応しています。"
                "より大きい入力には probabilistic=True を指定してください。"
            )

        # n の大きさに応じた最小の底集合を選ぶ
        for threshold, bases in self._DETERMINISTIC_TABLE:
            if n < threshold:
                return bases

    @staticmethod
    def _witness(n: int, a: int, d: int, s: int) -> bool:
        """
        底aによるミラー・ラビンのテストを1回実行する。

        n - 1 = 2^s * d (dは奇数) と分解済みであること。
        返り値がTrueなら「この底では合成数と見破れなかった」(nは素数かもしれない)、
        Falseなら「この底でnは合成数と断定できた」(aはnのwitness)。
        """
        a %= n
        # aがnの倍数の時はこの底では何も判定できないので通過扱いにする
        if a == 0:
            return True

        x = pow(a, d, n)
        if x == 1 or x == n - 1:
            return True

        # x を s-1 回まで平方し、途中で -1 (= n - 1) に到達するか調べる
        for _ in range(s - 1):
            x = x * x % n
            if x == n - 1:
                return True

        return False


def main():
    L, R = map(int, input().split())

    border = 45
    r = R // border
    if r < 7:
        print(-1)
        return

    miller_rabin = MillerRabin()
    while r >= 7 and r * border >= L:
        if miller_rabin.is_prime(r):
            print(r * border)
            return
        r -= 1

    print(-1)
    
    







if __name__ == "__main__":
    main()