#521638 (PyPy3) No.1140 EXPotentiaLLL!

• 問題: No.1140 EXPotentiaLLL!
• ユーザー: xuanji
• 提出日時: 2020-07-31 21:44:29
• 言語: PyPy3 (7.3.15)
• 結果: AC
• 実行時間: 588 ms / 2,000 ms
• コード長: 1,575 bytes
• コンパイル時間: 249 ms
• コンパイル使用メモリ: 82,304 KB
• 実行使用メモリ: 141,056 KB
• 最終ジャッジ日時: 2024-07-06 17:26:42
• 合計ジャッジ時間: 8,160 ms
• ジャッジサーバーID （参考情報）: judge1 / judge5

ファイルパターン	結果
sample	AC * 1
other	AC * 12

ソースコード

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
#!/usr/bin/env pypy3
from sys import stdin, stdout
 
def input():
    return stdin.readline().strip()
import math
class Sieve:
    def __init__(self, n=5*10**6+100):
        self.N = n
        s = [-1] * n
        for i in range(2, int(n**0.5)+1):
            if s[i] != -1: continue
            for j in range(i, n, i): 
                if j > i: s[j] = i
        self.s = s
        self.PRIMES = self.primes()
        # print(len(self.PRIMES))
    
    def primes(self):
        return [i for i, e in enumerate(self.s) if e == -1 and i >= 2]
    def fastfactorize(self, n):
        assert(n <= self.N)
        ret = []
        while self.s[n] != -1:
            ret += [self.s[n]]
            n = n // self.s[n]
        ret += [n]
        return ret
    def isprime(self, n):
        if n < self.N:
            return self.s[n] == -1
        for p in self.PRIMES:
            if p*p > n:
                return True
            if n % p == 0:
                return False
    def factorize(self, n):
        if n < self.N:
            return self.fastfactorize(n)
        
        for p in self.PRIMES:
            if p*p > n:
                break
            if n % p == 0:
                return [p] + self.factorize(n // p)
        return [n]
sieve = Sieve()
def ans(A, P):
    if P in [0,1]:
        return -1
    if sieve.s[P] == -1:
        if A % P == 0: return 0
        return 1
    return -1
 
T = int(input())
for _ in range(T):
    AP = input().split(' ')
    A = int(AP[0])
    P = int(AP[1])
    A = int(A)
    P = int(P)
    print(ans(A, P))
 
 
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX