Kiểm tra mảng có thể đồng nhất bằng nhân các số nguyên tố cho trước trong Python

Cho mảng nums và mảng số nguyên tố primes. Kiểm tra có thể nhân các phần tử của nums với các số trong primes (mỗi số dùng bao nhiêu lần cũng được) để tất cả phần tử bằng nhau hay không.

Ví dụ: nums=[25,100], primes=[2,5] → 25 × 2 × 2 = 100 → True.

Thuật toán

1. Tính LCM (bội chung nhỏ nhất) của tất cả phần tử trong nums.
2. Với mỗi nums[i], tính val = LCM / nums[i].
3. Phân tích val chỉ bằng các số trong primes. Nếu còn dư thừa số khác → False.

Triển khai

from math import gcd

def array_lcm(nums):
    ans = nums[0]
    for i in range(1, len(nums)):
        ans = (nums[i] * ans) // gcd(nums[i], ans)
    return ans

def solve(nums, primes):
    lcm_arr = array_lcm(nums)
    for i in range(len(nums)):
        val = lcm_arr // nums[i]
        for p in primes:
            while val % p == 0:
                val //= p
        if val != 1:
            return False
    return True

nums = [25, 100]
primes = [2, 5]
print(solve(nums, primes))  # True

Đầu vào / Đầu ra

Input: [25, 100], [2, 5]
Output: True