結果
| 問題 |
No.1036 Make One With GCD 2
|
| コンテスト | |
| ユーザー |
 qwewe
|
| 提出日時 | 2025-05-14 13:14:06 |
| 言語 | PyPy3 (7.3.15) |
| 結果 |
TLE
|
| 実行時間 | - |
| コード長 | 6,594 bytes |
| コンパイル時間 | 319 ms |
| コンパイル使用メモリ | 82,688 KB |
| 実行使用メモリ | 179,244 KB |
| 最終ジャッジ日時 | 2025-05-14 13:15:29 |
| 合計ジャッジ時間 | 22,818 ms |
|
ジャッジサーバーID （参考情報） |
judge2 / judge4 |
（要ログイン）
| ファイルパターン | 結果 |
|---|---|
| sample | AC * 4 |
| other | AC * 34 TLE * 1 -- * 6 |
ソースコード
import math
import sys
# Utilize math.gcd for efficient Greatest Common Divisor calculation.
# Python's built-in math.gcd is implemented in C and is generally fast.
# It handles large integers automatically due to Python's arbitrary precision integers.
def solve():
# Read input N, the number of elements in the array.
# Use sys.stdin.readline for faster input reading compared to input().
N = int(sys.stdin.readline())
# Read the array elements A_1, A_2, ..., A_N.
# Map the string inputs to integers.
A = list(map(int, sys.stdin.readline().split()))
# Initialize the total count of contiguous subarrays whose GCD is 1.
total_count = 0
# `current_gcd_info` stores information about GCDs of subarrays ending at the previous index (r-1).
# It is a list of tuples `(k, g)`.
# `k` is the starting index (0-based) of a contiguous range of starting positions.
# `g` is the GCD of subarrays `A[l...r-1]` for all `l` starting from `k` up to the start of the next range.
# Specifically, `k` is the *leftmost* starting index such that `gcd(A[k...r-1]) = g`.
# The list is maintained sorted by `k` in increasing order.
# The number of pairs in this list is bounded by O(log(max(A_i))).
current_gcd_info = []
# Iterate through the array A with index `r` from 0 to N-1.
# In each iteration, `r` represents the right endpoint of the contiguous subarrays being considered.
for r in range(N):
# `new_gcd_info_temp` will store candidate pairs `(k, g)` for subarrays ending at the current index `r`.
# `g = gcd(A[k...r])`.
new_gcd_info_temp = []
# Step 1: Consider the subarray containing only the element A[r].
# This subarray starts at index `r` and ends at index `r`. Its GCD is A[r].
# Add this base case pair `(r, A[r])` to the temporary list.
new_gcd_info_temp.append((r, A[r]))
# Step 2: Update the GCD information from the previous step (subarrays ending at r-1).
# For each pair `(k, g)` in `current_gcd_info`, where `g = gcd(A[k...r-1])`,
# we compute the GCD for the extended subarray `A[k...r]`.
# This new GCD is `gcd(g, A[r])`.
for k, g in current_gcd_info:
# Calculate the new GCD value.
new_g = math.gcd(g, A[r])
# Add the updated pair `(k, new_g)` to the temporary list.
new_gcd_info_temp.append((k, new_g))
# Step 3: Merge the generated candidate pairs to maintain the required properties.
# The temporary list `new_gcd_info_temp` might contain multiple pairs with the same GCD value `g`,
# or pairs where `g` is the same as the GCD of a range starting further left.
# We need to keep only the distinct GCD values `g`, associated with their *leftmost* starting index `k`.
# First, sort the temporary list by starting index `k`. This makes merging easier.
# The size of this list is O(log(max(A_i))), so sorting is fast: O(log(max A_i) * log(log(max A_i))).
new_gcd_info_temp.sort(key=lambda x: x[0])
# Perform the merge operation.
merged_gcd_info = []
if new_gcd_info_temp: # Proceed only if the list is not empty.
# Add the first pair (the one with the smallest `k`) unconditionally.
merged_gcd_info.append(new_gcd_info_temp[0])
# Keep track of the GCD value `g` of the last pair added to `merged_gcd_info`.
last_g = new_gcd_info_temp[0][1]
# Iterate through the rest of the sorted temporary pairs.
for i in range(1, len(new_gcd_info_temp)):
k, g = new_gcd_info_temp[i]
# If the current GCD `g` is different from the `last_g`, it means this pair
# starts a new distinct GCD value range. Add it to `merged_gcd_info`.
if g != last_g:
merged_gcd_info.append((k, g))
# Update `last_g` to the current GCD `g`.
last_g = g
# If `g == last_g`, this pair `(k, g)` is redundant. The previously added pair
# in `merged_gcd_info` already covers this GCD value `g` starting from an earlier
# index (`last_k <= k`). We only want the pair with the minimum `k`, so we skip this one.
# Update `current_gcd_info` to be the `merged_gcd_info` for the next iteration (r+1).
current_gcd_info = merged_gcd_info
# Step 4: Calculate the contribution to the `total_count` from subarrays ending at index `r`.
# Iterate through the finalized `current_gcd_info` list for index `r`.
num_pairs = len(current_gcd_info)
for i in range(num_pairs):
# Get the starting index `k_i` and GCD value `g_i` for the i-th range.
k_i, g_i = current_gcd_info[i]
# We are only interested in subarrays whose GCD is 1.
if g_i == 1:
# If the GCD is 1, this pair `(k_i, 1)` indicates that `gcd(A[l...r]) = 1`
# for all starting indices `l` within a certain range `[k_i, end_l]`.
# Determine the end index `end_l` of this range.
if i + 1 < num_pairs:
# If there is a next pair `(k_{i+1}, g_{i+1})`, the current range of `l`
# ends just before the start of the next range, i.e., at `k_{i+1} - 1`.
k_next = current_gcd_info[i+1][0]
end_l = k_next - 1
else:
# If this is the last pair in `current_gcd_info`, the range of `l`
# extends up to the current endpoint `r`.
end_l = r
# The number of valid starting indices `l` in the interval `[k_i, end_l]` is `end_l - k_i + 1`.
# Each such `l` corresponds to a subarray `A[l...r]` with GCD 1.
num_subarrays = end_l - k_i + 1
# Add this count to the total count.
total_count += num_subarrays
# After iterating through all possible right endpoints `r`, `total_count` holds the final answer.
# Print the total count. Use `sys.stdout.write` and `str()` conversion for potentially faster output.
# Adding a newline character as required by the problem statement.
sys.stdout.write(str(total_count) + '\n')
# Call the main function to solve the problem when the script is executed.
if __name__ == '__main__':
solve()