資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚研究
法律研究Python程式：查詢不同子序列的最大公約數
假設我們有一個包含正數的陣列 nums。我們需要找到 nums 所有非空子序列中不同最大公約數的數量。眾所周知，一個數字序列的最大公約數是指能整除該序列中所有數字的最大值。
例如，如果輸入為 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 所有不同數字的新集合
ans := 0
對於 x 從 1 到 T - 1，執行以下操作：
g := 0
對於 y 從 x 到 T - 1，每次遞增 x，執行以下操作：
如果 y 在 nums 中，則
g := gcd(g, y)
如果 g 等於 x，則
退出迴圈
如果 g 等於 x，則
ans := ans + 1
返回 ans
示例
讓我們看看下面的實現以更好地理解
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
更新於: 2021年10月8日
140 次瀏覽
廣告