結果

問題 No.3485 Find 495-like Number
コンテスト
ユーザー titia
提出日時 2026-03-27 22:31:12
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 388 ms / 5,000 ms
コード長 2,502 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 357 ms
コンパイル使用メモリ 85,444 KB
実行使用メモリ 190,464 KB
最終ジャッジ日時 2026-03-27 22:31:33
合計ジャッジ時間 18,973 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

import sys
input = sys.stdin.readline


# https://qiita.com/t_fuki/items/7cd50de54d3c5d063b4a#%E3%83%9F%E3%83%A9%E3%83%BC%E3%83%A9%E3%83%93%E3%83%B3%E7%B4%A0%E6%95%B0%E5%88%A4%E5%AE%9A%E6%B3%95
def is_prime(n):
    if n == 2:  # 2であれば素数なので終了
        return 1
    if n == 1 or n%2 == 0:  # 1もしくは2より大きい偶数であれば素数でないので終了
        return 0

    m = n - 1
    lsb = m & -m  # LSB. m-1をビット列で表した時立っているビットのうち最も小さいもの
    s = lsb.bit_length()-1  # 上述のs. LSB以上のビットの部分をdとし、2^s = LSBとすると上述のp-1 = 2^sdを満たす
    d = m // lsb

    test_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]

    for a in test_numbers:
        if a == n:  # a = n -> 任意の自然数kについてa^k ≡ 0(mod n)なので無視
            continue
        x = pow(a,d,n)  # x ≡ a^d(mod n)で初期化
        r = 0
        if x == 1:  # a^d ≡ 1(mod n)なので無視
            continue
        while x != m:  # r = 0からsまで順にx ≡ a^(2^rd) ≡ -1(mod n)を検証
            x = pow(x,2,n)
            r += 1
            if x == 1 or r == s:  # x ≡ 1(mod n) -> x^2 ≡ 1(mod n)で-1になり得ないので合成数
                return 0
    return 1  # すべてのテストを通過したら素数であるとして終了

x=10**7

# x以下の素数の列挙,素因数分解,約数の列挙
    
import math 
L=math.floor(math.sqrt(x)) # 平方根を求める

Primelist=[i for i in range(x+1)]
Primelist[1]=0 # 1は素数でないので0にする.
 
for i in Primelist:
    if i>L:
        break
    if i==0:
        continue
    for j in range(2*i,x+1,i):
        Primelist[j]=0

Primes=[Primelist[j] for j in range(x+1) if Primelist[j]!=0]

ANS=-1

L,R=list(map(int,input().split()))

for i in range(1,len(Primes)):
    x=Primes[i]
    if x>5000:
        break
    for j in range(i+1,len(Primes)):
        y=Primes[j]
        if x*x*y*y>R:
            break

        k=L//(x*x*y)

        while True:
            while x*x*y*k<L:
                k+=1
            if x*x*y*k>R:
                break
                
            if is_prime(k):
                if L<=x*x*y*k<=R:
                    print(x*x*y*k)
                    exit()
                elif x*x*y*k>R:
                    break
                else:
                    k+=1
            else:
                k+=1
                    
            

print(-1)
0