結果
問題 | No.2570 最大最大公約数 |
ユーザー |
![]() |
提出日時 | 2024-11-29 00:48:28 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 140 ms / 2,000 ms |
コード長 | 2,604 bytes |
コンパイル時間 | 263 ms |
コンパイル使用メモリ | 82,176 KB |
実行使用メモリ | 77,444 KB |
最終ジャッジ日時 | 2024-11-29 00:48:33 |
合計ジャッジ時間 | 4,128 ms |
ジャッジサーバーID (参考情報) |
judge1 / judge2 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 1 |
other | AC * 28 |
ソースコード
def gcd(a, b):while a:a, b = b%a, areturn bdef is_prime(n):if n == 2:return 1if n == 1 or n%2 == 0:return 0m = n - 1lsb = m & -ms = lsb.bit_length()-1d = m // lsbtest_numbers = [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37]for a in test_numbers:if a == n:continuex = pow(a,d,n)r = 0if x == 1:continuewhile x != m:x = pow(x,2,n)r += 1if x == 1 or r == s:return 0return 1def find_prime_factor(n):if n%2 == 0:return 2m = int(n**0.125)+1for c in range(1,n):f = lambda a: (pow(a,2,n)+c)%ny = 0g = q = r = 1k = 0while g == 1:x = ywhile k < 3*r//4:y = f(y)k += 1while k < r and g == 1:ys = yfor _ in range(min(m, r-k)):y = f(y)q = q*abs(x-y)%ng = gcd(q,n)k += mk = rr *= 2if g == n:g = 1y = yswhile g == 1:y = f(y)g = gcd(abs(x-y),n)if g == n:continueif is_prime(g):return gelif is_prime(n//g):return n//gelse:return find_prime_factor(g)def factorize(n):res = []while not is_prime(n) and n > 1: # nが合成数である間nの素因数の探索を繰り返すp = find_prime_factor(n)s = 0while n%p == 0: # nが素因数pで割れる間割り続け、出力に追加n //= ps += 1res.append((p, s))if n > 1: # n>1であればnは素数なので出力に追加res.append((n, 1))return resdef divisor(n):ans = [1]pf = factorize(n)for p, c in pf:L = len(ans)for i in range(L):v = 1for _ in range(c):v *= pans.append(ans[i]*v)return sorted(ans)N, K = map(int, input().split())A = list(map(int, input().split()))ans = 1for op in range(-K, K+1):div = divisor(A[0]+op)for d in div[::-1]:r = K-abs(op)for i in range(1, N):left = A[i]%dright = d-leftr -= min(left, right)if r < 0:breakelse:ans = max(ans, d)breakprint(ans)