結果

問題 No.308 素数は通れません
ユーザー antaanta
提出日時 2015-12-01 01:54:03
言語 PyPy3
(7.3.15)
結果
RE  
(最新)
AC  
(最初)
実行時間 -
コード長 1,555 bytes
コンパイル時間 328 ms
コンパイル使用メモリ 87,164 KB
実行使用メモリ 90,500 KB
最終ジャッジ日時 2023-08-18 13:00:12
合計ジャッジ時間 25,451 ms
ジャッジサーバーID
（参考情報） 		judge14 / judge15
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 RE -
testcase_01 RE -
testcase_02 RE -
testcase_03 RE -
testcase_04 RE -
testcase_05 RE -
testcase_06 RE -
testcase_07 RE -
testcase_08 RE -
testcase_09 RE -
testcase_10 RE -
testcase_11 RE -
testcase_12 RE -
testcase_13 RE -
testcase_14 RE -
testcase_15 RE -
testcase_16 RE -
testcase_17 RE -
testcase_18 RE -
testcase_19 RE -
testcase_20 RE -
testcase_21 RE -
testcase_22 RE -
testcase_23 RE -
testcase_24 RE -
testcase_25 RE -
testcase_26 RE -
testcase_27 RE -
testcase_28 RE -
testcase_29 RE -
testcase_30 RE -
testcase_31 RE -
testcase_32 RE -
testcase_33 RE -
testcase_34 RE -
testcase_35 RE -
testcase_36 RE -
testcase_37 RE -
testcase_38 RE -
testcase_39 RE -
testcase_40 RE -
testcase_41 RE -
testcase_42 RE -
testcase_43 RE -
testcase_44 RE -
testcase_45 RE -
testcase_46 RE -
testcase_47 RE -
testcase_48 RE -
testcase_49 RE -
testcase_50 RE -
testcase_51 RE -
testcase_52 RE -
testcase_53 RE -
testcase_54 RE -
testcase_55 RE -
testcase_56 RE -
testcase_57 RE -
testcase_58 RE -
testcase_59 RE -
testcase_60 RE -
testcase_61 RE -
testcase_62 RE -
testcase_63 RE -
testcase_64 RE -
testcase_65 RE -
testcase_66 RE -
testcase_67 RE -
testcase_68 RE -
testcase_69 RE -
testcase_70 RE -
testcase_71 RE -
testcase_72 RE -
testcase_73 RE -
testcase_74 RE -
testcase_75 RE -
testcase_76 RE -
testcase_77 RE -
testcase_78 RE -
testcase_79 RE -
testcase_80 RE -
testcase_81 RE -
testcase_82 RE -
testcase_83 RE -
testcase_84 RE -
testcase_85 RE -
testcase_86 RE -
testcase_87 RE -
testcase_88 RE -
testcase_89 RE -
testcase_90 RE -
testcase_91 RE -
testcase_92 RE -
testcase_93 RE -
testcase_94 RE -
testcase_95 RE -
testcase_96 RE -
testcase_97 RE -
testcase_98 RE -
testcase_99 RE -
testcase_100 RE -
testcase_101 RE -
testcase_102 RE -
testcase_103 RE -
testcase_104 RE -
testcase_105 RE -
testcase_106 RE -
権限があれば一括ダウンロードができます

ソースコード

diff # 

from fractions import gcd

def suspect(a, s, d, n):
	x = pow(a, d, n)
	if x == 1:
		return True
	for r in range(s):
		if x == n - 1:
			return True
		x = x * x % n
	return False

def isPrime(n):
	if n <= 1 or (n > 2 and n % 2 == 0):
		return False
	test = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]
	d, s = n - 1, 0
	while d % 2 == 0:
		s += 1
		d //= 2
	for a in test:
		if a >= n:
			break
		if not suspect(a, s, d, n):
			return False
	return True

def getNext(n, W, N):
	i, j = (n - 1) // W, (n - 1) % W
	for dy, dx in [(0,1),(1,0),(0,-1),(-1,0)]:
		yy, xx = i + dy, j + dx
		if yy < 0 or xx < 0 or xx >= W:
			continue
		m = yy * W + xx + 1
		if m > N or isPrime(m):
			continue
		yield m

def search(W, N):
	ds = [d for d in range(0,W) if gcd(d,W) != 1]
	vis, dvis = {}, {}
	q = [1]
	vis[1] = True
	h = 0
	while h < len(q):
		n = q[h]
		if n == N:
			return 0
		h += 1
		if gcd(n % W, W) > 1:
			if not n % W in dvis:
#				print("%d: %d, %d" % (W, n % W, n))
				dvis[n % W] =  True
				if len(dvis) == len(ds):
					break
		for m in getNext(n, W, N):
			if not m in vis:
				vis[m] = True
				q.append(m)
	return len(dvis) == len(ds) and 1 or 2

def search2(W, N):
	vis = {}
	q = [N]
	vis[N] = True
	h = 0
	while h < len(q):
		n = q[h]
		if gcd(n % W, W) > 1:
			return True
		h += 1
		for m in getNext(n, W, N):
			if not m in vis:
				vis[m] = True
				q.append(m)
	return False

N = int(input())
W = 2
ok = False
while True:
	if ok:
		break
	res = search(W, N)
	if res == 0:
		break
	if res == 1:
		if search2(W, N):
			break
	W += 1
print(W)
0