結果

問題 No.1036 Make One With GCD 2
ユーザー qwewe
提出日時 2025-05-14 12:58:28
言語 PyPy3
(7.3.15)
結果
TLE  
実行時間 -
コード長 4,502 bytes
コンパイル時間 365 ms
コンパイル使用メモリ 82,176 KB
実行使用メモリ 187,264 KB
最終ジャッジ日時 2025-05-14 12:59:42
合計ジャッジ時間 14,923 ms
ジャッジサーバーID
（参考情報） 		judge1 / judge5
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 4
other AC * 34 TLE * 1 -- * 6
権限があれば一括ダウンロードができます

ソースコード

diff # 

# -*- coding: utf-8 -*-

import math
import sys

# Use sys.stdin.readline for faster input processing compared to standard input()
# This is important in competitive programming to avoid Time Limit Exceeded on large inputs.
input = sys.stdin.readline

# Define the gcd function. Using math.gcd is generally efficient as it's often implemented in C.
# This function is crucial for the algorithm's performance.
def gcd(a, b):
    """Computes the greatest common divisor of non-negative integers a and b."""
    # math.gcd handles edge cases like gcd(x, 0) = x.
    # Since problem constraints state A_i >= 1, inputs to gcd will always be positive integers.
    return math.gcd(a, b)

def solve():
    """Solves the problem: Count contiguous subarrays with GCD equal to 1."""
    
    # Read the number of elements N
    N = int(input())
    
    # Handle the edge case N=0. Although constraints say N >= 1, it's safe practice.
    # If N=0, there are no subarrays, so the count is 0.
    if N == 0:
        print(0)
        return
        
    # Read the array elements A into a list of integers.
    A = list(map(int, input().split()))

    # Initialize the total count of subarrays whose GCD is 1.
    total_count = 0
    
    # Initialize the DP state dictionary.
    # `current_dp` stores the state for subarrays ending at the *previous* index (j-1).
    # It maps a GCD value `g` to the number of subarrays ending at index j-1 having GCD `g`.
    # It starts empty before processing the first element (index 0).
    current_dp = {} 

    # Iterate through the array elements using index `j` from 0 to N-1.
    for j in range(N):
        # Initialize the DP state dictionary for the *current* index `j`.
        # `next_dp` will store the mapping {gcd_value: count} for subarrays ending at index `j`.
        next_dp = {}
        
        # Get the value of the current element A[j].
        current_val = A[j]
        
        # --- Dynamic Programming Transition ---
        # Iterate through the items (GCD `g`, count `count`) in the DP state `current_dp` from the previous index `j-1`.
        for g, count in current_dp.items():
            # Calculate the new GCD value `new_g` by incorporating the current element `A[j]`.
            # This represents extending subarrays ending at `j-1` with GCD `g` by appending `A[j]`.
            
            # Optimization: If the previous GCD `g` was already 1, the GCD of the extended subarray will also be 1.
            # gcd(1, x) = 1 for any x >= 1.
            if g == 1:
                new_g = 1
            else:
                # Otherwise, compute the GCD of the previous GCD `g` and the current element `current_val`.
                new_g = gcd(g, current_val)

            # Update the count for this `new_g` in the DP state for the current index `j` (`next_dp`).
            # We use `dict.get(key, 0)` to safely handle cases where `new_g` might not yet be a key in `next_dp`.
            # This adds `count` (the number of subarrays ending at j-1 with GCD g)
            # to the count of subarrays ending at j with GCD `new_g`.
            next_dp[new_g] = next_dp.get(new_g, 0) + count
        
        # Account for the new subarray that consists solely of the current element `A[j]`.
        # This subarray is `[A[j]]`. Its GCD is simply `A[j]`.
        # Increment the count for GCD `current_val` in `next_dp` by 1.
        next_dp[current_val] = next_dp.get(current_val, 0) + 1
        
        # --- Update Total Count ---
        # After computing all GCDs for subarrays ending at index `j`,
        # check if GCD value 1 exists as a key in the `next_dp` state dictionary.
        # If it exists, it means there are `next_dp[1]` subarrays ending at `j` whose GCD is 1.
        # Add this count to the `total_count`.
        # Use `dict.get(1, 0)` to safely get the count, returning 0 if key 1 is not present (no subarrays ending at j have GCD 1).
        total_count += next_dp.get(1, 0)
            
        # --- Update DP State for Next Iteration ---
        # The computed state `next_dp` for the current index `j` becomes the `current_dp` state
        # for the next iteration (processing index `j+1`).
        current_dp = next_dp 

    # After iterating through all elements from j=0 to N-1, `total_count` holds the final answer.
    # Print the final total count. Python's `print` function automatically adds a newline at the end.
    print(total_count)

# Execute the solve function to run the solution logic.
solve()
0