ลบสมาชิกน้อยที่สุดเพื่อเพิ่ม GCD ของอาร์เรย์
กำหนดอาร์เรย์ N ตัวเลข ต้องการหาจำนวนสมาชิกที่ต้องลบน้อยที่สุด เพื่อให้ GCD ของสมาชิกที่เหลือ มากกว่า GCD เดิมของอาร์เรย์ทั้งหมด
ตัวอย่าง: [6, 9, 15, 30] → GCD เดิม = 3 ลบ 6, 9 เหลือ [15, 30] GCD = 15 > 3 → ลบ 2 ตัว
แนวคิดหลัก
- คำนวณ GCD ทั้งอาร์เรย์ เรียกว่า
g - หารทุกสมาชิกด้วย
g→ ได้อาร์เรย์ใหม่ที่ GCD = 1 - แยกตัวประกอบเฉพาะของแต่ละสมาชิก (ใช้ Sieve สำหรับหา SPF - Smallest Prime Factor)
- นับความถี่ของแต่ละเฉพาะที่ปรากฏในอาร์เรย์
- เฉพาะที่ปรากฏบ่อยที่สุด → เก็บสมาชิกที่มีเฉพาะนั้นไว้ ลบอีกส่วน → ได้ GCD ใหม่ที่มากกว่าเดิม
- คำตอบ =
N - max_frequency
โค้ดตัวอย่าง Python
from math import gcd as __gcd
INF = 100001
spf = [i for i in range(INF)]
def sieve():
for i in range(4, INF, 2):
spf[i] = 2
for i in range(3, INF):
if i * i > INF:
break
if spf[i] == i:
for j in range(2 * i, INF, i):
if spf[j] == j:
spf[j] = i
def calc_fact(x):
ret = []
while x != 1:
ret.append(spf[x])
x //= spf[x]
return ret
def minRemove(a, n):
g = 0
for i in range(n):
g = __gcd(a[i], g)
my_map = {}
for i in range(n):
a[i] //= g
for i in range(n):
p = calc_fact(a[i])
s = set(p)
for prime in s:
my_map[prime] = my_map.get(prime, 0) + 1
minimum = 10**9
for prime, cnt in my_map.items():
if (n - cnt) <= minimum:
minimum = n - cnt
return minimum if minimum != 10**9 else -1
# ตัวอย่าง
a = [6, 9, 15, 30]
sieve()
print(minRemove(a, len(a))) # 2
