type
status
date
slug
summary
tags
category
icon
password
创建时间
Apr 12, 2025 09:47 AM
给你一个由 正整数 组成的数组
nums。如果一个数组
arr 满足 prod(arr) == lcm(arr) * gcd(arr)，则称其为 乘积等价数组 ，其中：prod(arr)表示arr中所有元素的乘积。
gcd(arr)表示arr中所有元素的最大公因数 ()。
GCD
lcm(arr)表示arr中所有元素的最小公倍数 ()。
LCM
返回数组
nums 的 最长 乘积等价 子数组 的长度。不定长滑动窗口
这道题一点思路没有。看了题解，原来是数论的题！！！5555
任何正整数都可以表示为质因数的乘积：
设
a = p1^x1 * p2^x2 * ... * pn^xn, b = p1^y1 * p2^y2 * ... * pn^yn，其中 pi 是质数，xi 和 yi 是对应的指数（可以为 0）那么有
a * b = p1^(x1+y1) * p2^(x2+y2) * ... * pn^(xn+yn)对于最大公约数 gcd(a,b) 取每个质因数的最小指数:
gcd(a,b) = p1^min(x1,y1) * p2^min(x2,y2) * ... * pn^min(xn,yn)对于最小公倍数 lcm(a,b)，取每个质因数的最大指数：
lcm(a,b) = p1^max(x1,y1) * p2^max(x2,y2) * ... * pn^max(xn,yn)因此，
gcd(a,b) * lcm(a,b)=p1^(min(x1,y1)+max(x1,y1)) * p2^(min(x2,y2)+max(x2,y2)) * ... * pn^(min(xn,yn)+max(xn,yn))对于任意两个数，其中一个质数的指数有
min(x,y) + max(x,y) = x + y，则必有 gcd(a,b) * lcm(a,b) = a * b。这里有推论，具体证明看 灵茶山艾府 的题解
当 时， 当且仅当 个 时成立。
也就是对于一组数来说，质因数的每个指数只能由其中一个数贡献。这意味着，如果 ，那么这 个数（a*b*c*.. 的这些数，不是因数）必须两两互质。两两互质，就是最大公约数为 1.
只能说秒啊！！！！