結果

問題 No.3485 Find 495-like Number
コンテスト
ユーザー 👑 binap
提出日時 2026-02-27 08:35:53
言語 PyPy3
(7.3.17)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 1,391 ms / 5,000 ms
コード長 808 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 442 ms
コンパイル使用メモリ 85,632 KB
実行使用メモリ 263,296 KB
最終ジャッジ日時 2026-03-27 21:02:37
合計ジャッジ時間 59,346 ms
ジャッジサーバーID
（参考情報） 		judge3_0 / judge1_1
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 34
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

M = 22500000

prime = [1 for i in range(M + 1)]
prime[0] = 0
prime[1] = 0
for x in range(2, M + 1):
	if prime[x]:
		y = 2 * x
		while y <= M:
			prime[y] = 0
			y += x

l, r = map(int, input().split())

if r - l >= 45000:
	r = l + 45000

g = [0 for i in range(r - l + 1)]
h = [[] for i in range(r - l + 1)]

for x in range(l, r + 1):
	g[x - l] = x

for x in range(2, M + 1):
	if prime[x]:
		start = (l + (x - 1)) // x * x
		end = r // x * x
		y = start
		while y <= end:
			while g[y - l] % x == 0:
				g[y - l] //= x;
				h[y - l].append(x)
			y += x

for x in range(l, r + 1):
	if g[x - l] != 1:
		h[x - l].append(g[x - l])
	
ans = -1
for x in range(l, r + 1):
	if len(h[x - l]) == 4:
		if h[x - l][0] == h[x - l][1] and h[x - l][1] != h[x - l][2] and h[x - l][2] != h[x - l][3]:
			ans = x

print(ans)
0