สมมติว่าเรามีจำนวนอาร์เรย์ที่มีค่าบวก เราต้องหาจำนวนของ GCD ที่แตกต่างกันในลำดับย่อยที่ไม่ว่างเปล่าของ nums ดังที่เราทราบ GCD ของลำดับตัวเลขเป็นค่าที่ยิ่งใหญ่ที่สุดที่หารตัวเลขทั้งหมดในลำดับอย่างเท่าเทียมกัน
ดังนั้น หากอินพุตเท่ากับ nums =[4,6,18] ผลลัพธ์จะเป็น 4 เพราะ gcd([4]) =4, gcd([6]) =6, gcd([18]) =18 gcd([4,6]) =2, gcd([4,18]) =2, gcd([6,18]) =6, gcd([4,6,18]) =2 ดังนั้นตัวเลขทั้งหมดจึงเป็น [ 4,6,18,2] มี 4 ตัว
เพื่อแก้ปัญหานี้ เราจะทำตามขั้นตอนเหล่านี้ -
-
T :=สูงสุด nums + 1
-
nums :=ชุดใหม่ที่มีจำนวน nums ที่แตกต่างกันทั้งหมด
-
ตอบ :=0
-
สำหรับ x ในช่วง 1 ถึง T - 1 ทำ
-
ก. :=0
-
สำหรับ y ในช่วง x ถึง T - 1 ให้อัปเดตในแต่ละขั้นตอนทีละ x ทำ
-
ถ้า y เป็นตัวเลข ดังนั้น
-
g :=gcd(g, y)
-
-
ถ้า g เท่ากับ x แล้ว
-
ออกมาจากลูป
-
-
-
ถ้า g เท่ากับ x แล้ว
-
ans :=ans + 1
-
-
-
กลับมาอีกครั้ง
ตัวอย่าง
ให้เราดูการใช้งานต่อไปนี้เพื่อความเข้าใจที่ดีขึ้น
from math import gcd def solve(nums): T = max(nums) + 1 nums = set(nums) ans = 0 for x in range(1, T): g = 0 for y in range(x, T, x): if y in nums: g = gcd(g, y) if g == x: break if g == x: ans += 1 return ans nums = [4,6,18] print(solve(nums))
อินพุต
[4,6,18]
ผลลัพธ์
4
