結果

問題 No.2682 Visible Divisible
ユーザー hiro1729hiro1729
提出日時 2024-03-21 07:21:51
言語 PyPy3
(7.3.15)
結果
AC  
実行時間 163 ms / 2,000 ms
コード長 2,529 bytes
コンパイル時間 326 ms
コンパイル使用メモリ 81,924 KB
実行使用メモリ 106,840 KB
最終ジャッジ日時 2024-09-30 10:01:09
合計ジャッジ時間 3,731 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge2
このコードへのチャレンジ
（要ログイン）

テストケース

テストケース表示
入力 結果 実行時間
実行使用メモリ
testcase_00 AC 151 ms
106,316 KB
testcase_01 AC 162 ms
106,800 KB
testcase_02 AC 163 ms
106,736 KB
testcase_03 AC 153 ms
106,828 KB
testcase_04 AC 132 ms
106,352 KB
testcase_05 AC 132 ms
105,820 KB
testcase_06 AC 117 ms
106,840 KB
testcase_07 AC 129 ms
106,260 KB
testcase_08 AC 42 ms
52,608 KB
testcase_09 AC 41 ms
52,352 KB
testcase_10 AC 41 ms
52,864 KB
testcase_11 AC 146 ms
106,336 KB
testcase_12 AC 139 ms
106,400 KB
testcase_13 AC 136 ms
106,680 KB
testcase_14 AC 153 ms
105,900 KB
testcase_15 AC 150 ms
106,372 KB
testcase_16 AC 139 ms
106,488 KB
権限があれば一括ダウンロードができます

ソースコード

diff # 

from math import gcd

# N≦2^64で素数判定
def is_prime(N: int) -> bool:
	if N <= 1:
		return False
	if N == 2:
		return True
	if N & 1 == 0:
		return False
	s = 0
	d = N - 1
	while d & 1 == 0:
		s += 1
		d >>= 1
	for a in [2, 325, 9375, 28178, 450775, 9780504, 1795265022]:
		if a % N == 0:
			return True
		x = pow(a, d, N)
		if x != 1:
			t = 0
			while t < s and x < N - 1:
				t += 1
				x = x * x % N
			if t == s:
				return False
	return True

# N以下の最大の素数を返す
def biggest_prime(N: int) -> int:
	while not is_prime(N):
		N -= 1
	return N

# N以上の最小の素数を返す
def smallest_prime(N: int) -> int:
	while not is_prime(N):
		N += 1
	return N

# エラトステネスの篩 [1, N]
def Eratosthenes_Sieve(N: int) -> list:
	if N < 2:
		return []
	p = [True] * (N + 1)
	p[0] = p[1] = False
	for i in range(2, N + 1):
		if i * i > N:
			break
		if p[i]:
			for j in range(2 * i, N + 1, i):
				p[j] = False
	return p

# エラトステネスの区間篩 [A, B]
def Eratosthenes_Sieve2(A: int, B: int) -> list:
	p = [True] * (B - A + 1)
	for i in range(2, B + 1):
		if i * i > B:
			break
		if i < A:
			for j in range((A + i - 1) // i * i, B + 1, i):
				p[j - A] = False
		elif p[i - A]:
			for j in range(2 * i, B + 1, i):
				p[j - A] = False
	return p

# 約数(ソートする)
def divisor(N: int) -> list:
	d = []
	d2 = []
	for i in range(1, N + 1):
		if i * i > N:
			break
		if N % i == 0:
			d.append(i)
			if i * i < N:
				d2.append(N // i)
	return d + d2[::-1]

# 素因数分解
def factorize(N: int) -> list:
	c = 0
	while N & 1 == 0:
		c += 1
		N >>= 1
	ans = [(2, c)]
	while N > 1:
		n = N
		while not is_prime(n):
			m = int(n ** 0.125) + 1
			for c in range(1, n):
				y = 0
				g = 1
				q = 1
				r = 1
				while g == 1:
					x = y
					for _ in range(r >> 1, (3 * r) >> 2):
						y = (y * y + c) % n
					for k in range((3 * r) >> 2, r, m):
						ys = y
						for _ in range(min(m, r - k)):
							y = (y * y + c) % n
							q = q * (x - y) % n
						g = gcd(q, n)
						if g != 1:
							break
					r <<= 1
				if g == n:
					g = 1
					y = ys
					while g == 1:
						y = (y * y + c) % n
						g = gcd(x - y, n)
				if g != n:
					break
			n = g
		c = 0
		while N % n == 0:
			c += 1
			N //= n
		ans.append((n, c))
	ans.sort()
	return ans

N, K = map(int, input().split())
A = list(map(int, input().split()))
for p, e in factorize(K):
	m = 0
	for i in A:
		c = 0
		while i % p == 0:
			i //= p
			c += 1
		m = max(m, c)
	if e > m:
		exit(print("No"))
print("Yes")
0