โจทย์: กำหนดอาร์เรย์ A ที่เก็บค่า GCD ของทุกคู่ที่เป็นไปได้ของอาร์เรย์ต้นฉบับ (ขนาด n) หาอาร์เรย์ต้นฉบับ (ขนาด √n)
ตัวอย่าง: A = [6, 1, 1, 13] → ต้นฉบับคือ [13, 6] เพราะ gcd(13,13)=13, gcd(13,6)=1, gcd(6,13)=1, gcd(6,6)=6
อัลกอริทึม
- เรียง A เรียงมากไปน้อย
- นับจำนวนครั้งที่แต่ละค่าปรากฏ (occurrence array)
- ขนาดอาร์เรย์ต้นฉบับ = √(len(A))
- วนลูปผ่าน A: ถ้าค่านั้นยังเหลือ occurrence > 0 → เป็นสมาชิกของอาร์เรย์ต้นฉบับ
- ลบ occurrence ของค่านั้น และลบ occurrence ของ GCD กับสมาชิกที่เลือกแล้ว (ลบ 2 ต่อคู่)
ตัวอย่างโค้ด
from math import sqrt, gcd
def get_actual_array(A):
n = len(A)
A.sort(reverse=True)
occurrence = [0] * (A[0] + 1)
for val in A:
occurrence[val] += 1
size = int(sqrt(n))
res = [0] * len(A)
l = 0
for i in range(n):
if occurrence[A[i]] > 0:
res[l] = A[i]
occurrence[res[l]] -= 1
l += 1
for j in range(l):
if i != j:
g = gcd(A[i], res[j])
occurrence[g] -= 2
return res[:size]
A = [6, 1, 1, 13]
print(get_actual_array(A)) # [13, 6]
ผลลัพธ์
[13, 6]
หลักการ: ค่ามากที่สุดใน A ต้องเป็นสมาชิกของอาร์เรย์ต้นฉบับ (เพราะ gcd(x,x)=x) หลังเลือกแล้ว ต้องลบ GCD ที่เกิดจากคู่ที่เกี่ยวข้องออกจาก occurrence
