結果
問題 |
No.28 末尾最適化
|
ユーザー |
![]() |
提出日時 | 2025-03-31 17:51:34 |
言語 | PyPy3 (7.3.15) |
結果 |
AC
|
実行時間 | 3,342 ms / 5,000 ms |
コード長 | 2,386 bytes |
コンパイル時間 | 194 ms |
コンパイル使用メモリ | 82,116 KB |
実行使用メモリ | 187,732 KB |
最終ジャッジ日時 | 2025-03-31 17:52:18 |
合計ジャッジ時間 | 4,064 ms |
ジャッジサーバーID (参考情報) |
judge3 / judge1 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
other | AC * 2 |
ソースコード
def generate_sequence(seed, N): mod = 100000009 X = [seed] for _ in range(N): prev = X[-1] val = (prev ** 2 + prev * 12345) % mod X.append(1 + val) return X def factorize(B): factors = [] p = 2 while p * p <= B: if B % p == 0: count = 0 while B % p == 0: count += 1 B = B // p factors.append((p, count)) p += 1 if B > 1: factors.append((B, 1)) return factors def compute_exponents(X, factors): exponents = [] for x in X: exps = [] for (p, _) in factors: count = 0 current_x = x while current_x % p == 0 and current_x != 0: count += 1 current_x = current_x // p exps.append(count) exponents.append(exps) return exponents import sys def main(): input = sys.stdin.read().split() ptr = 0 Q = int(input[ptr]) ptr += 1 for _ in range(Q): seed = int(input[ptr]) N = int(input[ptr+1]) K = int(input[ptr+2]) B = int(input[ptr+3]) ptr +=4 # Generate the X sequence X = generate_sequence(seed, N) # Factorize B factors = factorize(B) if not factors: print(0) continue # Compute exponents for each X_i exponents_list = compute_exponents(X, factors) m = len(factors) min_trailing = float('inf') # For each prime's selection (sorted by their exponents) for i in range(m): # Sort the exponents_list based on the i-th component (prime's exponents) sorted_exponents = sorted(exponents_list, key=lambda x: x[i]) selected = sorted_exponents[:K] # Sum each prime's exponents in the selected elements sums = [0] * m for exp in selected: for j in range(m): sums[j] += exp[j] # Compute trailing zeros for this selection current_trailing = min(sums[j] // factors[j][1] for j in range(m)) if current_trailing < min_trailing: min_trailing = current_trailing print(min_trailing) if __name__ == "__main__": main()