結果

問題 No.2682 Visible Divisible
ユーザー pitP
提出日時 2024-03-21 00:47:50
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,740 bytes
コンパイル時間 325 ms
コンパイル使用メモリ 81,920 KB
実行使用メモリ 120,056 KB
最終ジャッジ日時 2024-09-30 09:51:19
合計ジャッジ時間 5,270 ms
ジャッジサーバーID
(参考情報)
judge5 / judge3
このコードへのチャレンジ
(要ログイン)
ファイルパターン 結果
sample -- * 3
other AC * 2 TLE * 1 -- * 11
権限があれば一括ダウンロードができます

ソースコード

diff #
プレゼンテーションモードにする

# https://qiita.com/daikw/items/f48d6ac374255763463d
import math
import random
class Prime:
seed_primes = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97]
def is_prime(self, n):
"""
prime test (hybrid)
see also: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
:param n:
:return: boolean
"""
is_prime_common = self.is_prime_common(n)
if is_prime_common is not None:
return is_prime_common
if n < 2000000:
return self.is_prime_brute_force(n)
else:
return self.is_prime_miller_rabin(n)
def is_prime_common(self, n):
if n == 1: return False
if n in Prime.seed_primes: return True
if any(map(lambda x: n % x == 0, self.seed_primes)): return False
def is_prime_brute_force(self, n):
"""
brute force prime test
use with is_prime_common if you want to skip seed_primes
:param n:
:return: boolean
"""
for k in range(2, int(math.sqrt(n)) + 1):
if n % k == 0:
return False
return True
def is_prime_miller_rabin(self, n):
"""
miller rabin prime test
use with is_prime_common if you want to skip seed_primes
see also
algorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_test
implementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59
improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369
:param n:
:return: boolean
"""
d = n - 1
while d & 1 == 0:
d >>= 1
# use one of these lines / upper is more efficient.
witnesses = self.get_witnesses(n)
# witnesses = [random.randint(1, n - 1) for _ in range(100)]
for w in witnesses:
y = pow(w, d, n)
while d != n - 1 and y != 1 and y != n - 1:
y = (y * y) % n
d <<= 1
if y != n - 1 and d & 1 == 0:
return False
return True
def get_witnesses(self, num):
def _get_range(num):
if num < 2047:
return 1
if num < 1373653:
return 2
if num < 25326001:
return 3
if num < 3215031751:
return 4
if num < 2152302898747:
return 5
if num < 3474749660383:
return 6
if num < 341550071728321:
return 7
if num < 3825123056546413051:
return 9
return 12
return self.seed_primes[:_get_range(num)]
def gcd(self, a, b):
if a < b:
return self.gcd(b, a)
if b == 0:
return a
while b:
a, b = b, a % b
return a
@staticmethod
def f(x, n, seed):
"""
pseudo prime generator
:param x:
:param n:
:param seed:
:return: pseudo prime
"""
p = Prime.seed_primes[seed % len(Prime.seed_primes)]
return (p * x + seed) % n
def find_factor(self, n, seed=1):
"""
find one of factor of n
this function is based to Pollard's rho algorithm
see also
algorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithm
implementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98
:param n:
:param seed:
:return: factor
"""
if self.is_prime(n):
return n
x, y, d = 2, 2, 1
count = 0
while d == 1:
count += 1
x = self.f(x, n, seed)
y = self.f(self.f(y, n, seed), n, seed)
d = self.gcd(abs(x - y), n)
if d == n:
return self.find_factor(n, seed+1)
return self.find_factor(d)
def find_factors(self, n):
primes = {}
if self.is_prime(n):
primes[n] = 1
return primes
while n > 1:
factor = self.find_factor(n)
primes.setdefault(factor, 0)
primes[factor] += 1
n //= factor
return primes
prime = Prime()
N, K = map(int, input().split())
A = list(map(int, input().split()))
facts = prime.find_factors(K)
d = {}
p = facts.keys()
for key in facts.keys():
d[key] = 0
for i in range(N):
for key in p:
cnt = 0
while A[i] % key == 0:
cnt += 1
A[i] //= key
d[key] = max(d[key], cnt)
for key in p:
if d[key] < facts[key]:
exit(print("No"))
print("Yes")
הההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההההה
XXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXXX
0