/ SeriousOJ /

Record Detail

Wrong Answer


  
# Status Time Cost Memory Cost
#1 Wrong Answer 25ms 3.426 MiB
#2 Wrong Answer 26ms 3.523 MiB
#3 Wrong Answer 27ms 3.453 MiB
#4 Wrong Answer 28ms 3.555 MiB
#5 Wrong Answer 27ms 3.551 MiB
#6 Wrong Answer 28ms 3.555 MiB
#7 Wrong Answer 29ms 3.547 MiB
#8 Wrong Answer 31ms 3.461 MiB
#9 Wrong Answer 33ms 3.59 MiB
#10 Wrong Answer 38ms 3.676 MiB
#11 Wrong Answer 61ms 4.09 MiB
#12 Wrong Answer 71ms 4.133 MiB
#13 Wrong Answer 45ms 3.809 MiB
#14 Wrong Answer 48ms 3.828 MiB
#15 Wrong Answer 48ms 3.719 MiB
#16 Wrong Answer 48ms 3.84 MiB
#17 Wrong Answer 48ms 3.828 MiB
#18 Wrong Answer 43ms 3.703 MiB
#19 Wrong Answer 38ms 3.68 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
Submission
Problem
P1076 Even Odd GCD (Easy Version)
Contest
Bangladesh 2.0
Language
Python 3 (Python 3.12.3)
Submit At
2024-08-16 16:28:42
Judged At
2024-10-03 13:26:50
Judged By
Score
0
Total Time
71ms
Peak Memory
4.133 MiB