class Solution {
public:
long long singleDivisorTriplet(vector<int>& nums) {
}
};
2198. 单因数三元组
给定一个下标从 0 开始的正整数数组 nums。由三个 不同 索引 (i, j, k) 组成的三元组，如果 nums[i] + nums[j] + nums[k] 能被 nums[i]、nums[j] 或 nums[k] 中的 一个 整除，则称为 nums 的 单因数三元组。
返回 nums 的单因数三元组。
示例 1:
输入: nums = [4,6,7,3,2] 输出: 12 解释: 三元组索引 (0, 3, 4), (0, 4, 3), (3, 0, 4), (3, 4, 0), (4, 0, 3), 和 (4, 3, 0) 的值为 [4, 3, 2] (或者说排列为 [4, 3, 2]). 4 + 3 + 2 = 9 只能被 3 整除，所以所有的三元组都是单因数三元组。 三元组索引 (0, 2, 3), (0, 3, 2), (2, 0, 3), (2, 3, 0), (3, 0, 2), 和 (3, 2, 0) 的值为 [4, 7, 3] (或者说排列为 [4, 7, 3]). 4 + 7 + 3 = 14 只能被 7 整除，所以所有的三元组都是单因数三元组。 一共有 12 个单因数三元组。
示例 2:
输入: nums = [1,2,2] 输出: 6 提示: 三元组索引 (0, 1, 2), (0, 2, 1), (1, 0, 2), (1, 2, 0), (2, 0, 1), 和 (2, 1, 0) 的值为 [1, 2, 2] (或者说排列为 [1, 2, 2]). 1 + 2 + 2 = 5 只能被 1 整除，所以所有的三元组都是单因数三元组。 一共有6个单因数三元组。
示例 3:
输入: nums = [1,1,1] 输出: 0 提示: 没有单因数三元组。 注意 (0, 1, 2) 不是单因数三元组。 因为 nums[0] + nums[1] + nums[2] = 3，3 可以被 nums[0], nums[1], nums[2] 整除。
提示:
3 <= nums.length <= 1051 <= nums[i] <= 100原站题解
golang 解法, 执行用时: 88 ms, 内存消耗: 7.2 MB, 提交时间: 2023-10-22 10:20:25
func singleDivisorTriplet(nums []int) int64 {
factors := [101]int64{}
for _, num := range nums {
factors[num]++
}
ans := int64(0)
for i := 1; i <= 100; i++ {
if factors[i] == 0 {
continue
}
for j := i; j <= 100; j++ {
if factors[j] == 0 {
continue
}
for k := j; k <= 100; k++ {
if factors[k] == 0 {
continue
}
a, b, c := (i+j+k)%i, (i+j+k)%j, (i+j+k)%k
if (a != 0 && b == 0 && c != 0) || (a == 0 && b != 0 && c != 0) || (a != 0 && b != 0 && c == 0) {
if i == j && j == k {
ans += factors[i] * (factors[i] - 1) * (factors[i] - 2)
} else if i == j && j != k {
ans += factors[i] * (factors[i] - 1) * factors[k] *3
} else if i == k && j != k {
ans += factors[i] * (factors[i] - 1) * factors[j] *3
} else if j == k && i != j {
ans += factors[i] * factors[j] * (factors[j] - 1) *3
} else {
ans += factors[i] * factors[j] * factors[k] * 6
}
}
}
}
}
return ans
}
cpp 解法, 执行用时: 180 ms, 内存消耗: 57.6 MB, 提交时间: 2023-10-22 10:20:08
class Solution {
public:
long long singleDivisorTriplet(vector<int>& nums) {
vector<int> cnts(101, 0);
for(int i : nums) cnts[i]++;
long long res = 0;
for(int i = 1; i <= 100; ++i) {
for(int j = i; j <= 100; ++j) {
for(int k = j; k <= 100; ++k) {
int s = i + j + k;
if((s % i == 0) + (s % j == 0) + (s % k == 0) == 1) {
if(i != j && j != k) {
res += 6ll * cnts[i] * cnts[j] * cnts[k];
} else if(i == j) {
res += 3ll * cnts[i] * (cnts[i]-1) * cnts[k];
} else {
res += 3ll * cnts[i] * cnts[j] * (cnts[j]-1);
}
}
}
}
}
return res;
}
};
python3 解法, 执行用时: 2104 ms, 内存消耗: 20.3 MB, 提交时间: 2023-10-22 10:19:46
from typing import List
from collections import Counter
from itertools import product
class Solution:
def singleDivisorTriplet(self, nums: List[int]) -> int:
counter = Counter(nums)
res = 0
for n1, n2, n3 in product(counter.keys(), repeat=3):
if not n1 <= n2 <= n3:
continue
sum_ = n1 + n2 + n3
if sum(sum_ % n == 0 for n in (n1, n2, n3)) == 1:
good1 = next((n for n in (n1, n2, n3) if sum_ % n == 0))
bad1, bad2 = (n for n in (n1, n2, n3) if sum_ % n != 0)
if bad1 == bad2:
res += counter[good1] * counter[bad1] * (counter[bad1] - 1) * 3
else:
res += counter[good1] * counter[bad1] * counter[bad2] * 6
return res