結果

問題 No.3461 Min GCD
コンテスト
ユーザー 2251799813685248
提出日時 2026-11-05 18:06:45
言語 PyPy3
(8.0.1 + ACL)
コンパイル:
pypy3 -mpy_compile _filename_
実行:
pypy3 _filename_
結果
AC  
実行時間 555 ms / 2,000 ms
+ 872µs
コード長 2,988 bytes
記録
記録タグの例:
初AC ショートコード 純ショートコード 純主流ショートコード 最速実行時間
コンパイル時間 816 ms
コンパイル使用メモリ 64,728 KB
実行使用メモリ 92,124 KB
最終ジャッジ日時 2026-11-05 18:06:52
合計ジャッジ時間 6,906 ms
ジャッジサーバーID
（参考情報） 		judge4_0 / judge2_0
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 20
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

class Eratosthenes:
    # コンストラクタにNを渡すことでN以下の整数を扱える。
    def __init__(self, N):
        self.mark = [False] * (N + 1)
        self.primes = [] # N以下の素数リスト これは素因数分解をするうえではなくてもよい
        self.lpf = [-1] * (N + 1) # iを割り切る最小の素因数
        # ちなみに、lpfは最小素因数(least prime factor)の略称
        
        if N >= 1:
            self.mark[1] = True
            
        for i in range(2, N + 1):
            if not self.mark[i]: # iが素数のとき
                self.primes.append(i)
                self.lpf[i] = i # 素数のlpfはそれ自身
                for j in range(2 * i, N + 1, i):
                    self.mark[j] = True
                    if self.lpf[j] == -1: # まだjのlpfが決まっていないとき
                        self.lpf[j] = i # iにする
                        # iは小さい順なので、まだ決まっていないものを貪欲にiで書き換えることで、最初に書き込んだものが最小になってくれる

    # 単一の整数を素因数分解
    def factorize(self, x):
        if x == 1:
            return [[1, 0]]
        res = []
        # Pythonにはdo-whileがないため、whileで代用 (x >= 2であることが保証されているため同等)
        while x > 1:
            if not res or self.lpf[x] != res[-1][0]:
                res.append([self.lpf[x], 1])
            else:
                res[-1][1] += 1
            x //= self.lpf[x]
        return res
    def enumerate_mobius(self, N):
      res = [0]*(N+1)
      res[1] = 1
      for i in range(2, N+1):
        if i == self.lpf[i]:
          res[i] = -1
        else:
          if i//self.lpf[i]%self.lpf[i] == 0:
            res[i] = 0
          else:
            res[i] = res[self.lpf[i]]*res[i//self.lpf[i]]
      return res


def makediv_from_primes(p):
    d = [1]
    if p[0][0] == 1: # 1が入ってきたら例外処理
        return d
    
    for v in p: # 全方向を試す
        t = len(d)
        temp = 1
        for w in range(v[1]): # 実際に延長する。
            temp *= v[0]
            for i in range(t):
                d.append(d[i] * temp)
                
    d.sort()
    return d







E = Eratosthenes(100010)


N,K = map(int, input().split())
a = list(map(int, input().split()))
b = list(map(int, input().split()))

c = [0]*100010

for i,n in enumerate(a):
    temp = makediv_from_primes(E.factorize(n))
    temp2 = [9223372036854775807]*(len(temp)+1)
    for idx, m in enumerate(temp):
        temp2[idx] = (b[i]+m-1)//m*m-b[i]
    for idx in range(len(temp)-1, -1, -1):
        temp2[idx] = min(temp2[idx], temp2[idx+1])
    temp.append(100005)
    for idx in range(len(temp)-1):
        c[temp[idx]] -= temp2[idx+1]
        c[temp[idx+1]] += temp2[idx+1]

for i in range(100004, -1, -1):
    c[i] += c[i+1]
    if c[i] <= K:
        print(i)
        exit()
0