結果
問題 | No.2682 Visible Divisible |
ユーザー |
|
提出日時 | 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 |
ソースコード
# https://qiita.com/daikw/items/f48d6ac374255763463dimport mathimport randomclass 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_commonif 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 Falseif n in Prime.seed_primes: return Trueif any(map(lambda x: n % x == 0, self.seed_primes)): return Falsedef is_prime_brute_force(self, n):"""brute force prime testuse 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 Falsereturn Truedef is_prime_miller_rabin(self, n):"""miller rabin prime testuse with is_prime_common if you want to skip seed_primessee alsoalgorithm: https://en.wikipedia.org/wiki/Miller%E2%80%93Rabin_primality_testimplementation: https://qiita.com/srtk86/items/609737d50c9ef5f5dc59improvement: https://qiita.com/gushwell/items/ff9ed83ba55350aaa369:param n::return: boolean"""d = n - 1while 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) % nd <<= 1if y != n - 1 and d & 1 == 0:return Falsereturn Truedef get_witnesses(self, num):def _get_range(num):if num < 2047:return 1if num < 1373653:return 2if num < 25326001:return 3if num < 3215031751:return 4if num < 2152302898747:return 5if num < 3474749660383:return 6if num < 341550071728321:return 7if num < 3825123056546413051:return 9return 12return self.seed_primes[:_get_range(num)]def gcd(self, a, b):if a < b:return self.gcd(b, a)if b == 0:return awhile b:a, b = b, a % breturn a@staticmethoddef 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) % ndef find_factor(self, n, seed=1):"""find one of factor of nthis function is based to Pollard's rho algorithmsee alsoalgorithm: https://en.wikipedia.org/wiki/Pollard%27s_rho_algorithmimplementation: https://qiita.com/gushwell/items/561afde2e00bf3380c98:param n::param seed::return: factor"""if self.is_prime(n):return nx, y, d = 2, 2, 1count = 0while d == 1:count += 1x = 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] = 1return primeswhile n > 1:factor = self.find_factor(n)primes.setdefault(factor, 0)primes[factor] += 1n //= factorreturn primesprime = 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] = 0for i in range(N):for key in p:cnt = 0while A[i] % key == 0:cnt += 1A[i] //= keyd[key] = max(d[key], cnt)for key in p:if d[key] < facts[key]:exit(print("No"))print("Yes")