#61582 (PyPy3) No.308 素数は通れません

• 問題: No.308 素数は通れません
• ユーザー: anta
• 提出日時: 2015-12-01 01:54:03
• 言語: PyPy3 (7.3.15)
• 結果: RE (最新)
  AC
  (最初)
• 実行時間: -
• コード長: 1,555 bytes
• コンパイル時間: 456 ms
• コンパイル使用メモリ: 82,048 KB
• 実行使用メモリ: 88,832 KB
• 最終ジャッジ日時: 2024-11-27 18:09:52
• 合計ジャッジ時間: 18,614 ms
• ジャッジサーバーID （参考情報）: judge2 / judge1

ファイルパターン	結果
other	RE * 107

ソースコード

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
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)
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX