/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 20ms 3.48 MiB

Code

from math import gcd
from collections import defaultdict
import sys
input = sys.stdin.read

def get_divisors(num):
    divisors = set()
    for i in range(1, int(num**0.5) + 1):
        if num % i == 0:
            divisors.add(i)
            if i != num // i:
                divisors.add(num // i)
    return divisors

def max_gcd_sum(n, arr):
    if n == 1:
        return 0
    
    # Frequency map of divisors
    divisor_count = defaultdict(int)
    
    for num in arr:
        for div in get_divisors(num):
            divisor_count[div] += 1
    
    max_sum = 0
    
    # Check each possible divisor
    for d in sorted(divisor_count.keys(), reverse=True):
        count = divisor_count[d]
        if count >= (n + 1) // 2:
            max_sum = max(max_sum, 2 * d)
    
    return max_sum

def main():
    data = input().split()
    index = 0
    t = int(data[index])
    index += 1
    results = []
    
    for _ in range(t):
        n = int(data[index])
        index += 1
        arr = list(map(int, data[index:index + n]))
        index += n
        results.append(max_gcd_sum(n, arr))
    
    for result in results:
        print(result)

if __name__ == "__main__":
    main()

Information

Submit By
Type
Pretest
Problem
P1076 Even Odd GCD (Easy Version)
Language
Python 3 (Python 3.12.3)
Submit At
2024-08-16 16:28:40
Judged At
2024-10-03 13:26:51
Judged By
Score
0
Total Time
20ms
Peak Memory
3.48 MiB