Lishen Qu的博客
首页
News
Github
友情链接
往期整理
  •   历史归档
  •   文章分类
  •   文章标签
Lishen Qu
文章
7
分类
3
标签
4
首页
News
Github
友情链接
往期整理
历史归档
文章分类
文章标签
学习笔记
📚Leetcode-2183
发布于: 2024-10-12
最后更新: 2024-11-19
次查看
力扣
type
status
date
slug
summary
tags
category
icon
password

题目描述

链接

代码

理解

!! 最妙的点在于,为了求两个数乘积是 k 的倍数,那么把 k 拆成 k = a * b, 然后 nums[i] 是a 的倍数,nums[j] 是 b 的倍数。对于一个固定的 nums[j], nums[i]必须是某一个数 a 的倍数,为了找到尽可能多的 i,那么 a 必须尽可能的小,即 b 必须尽可能的大, 所以 b 应该是 k 和 nums[j] 的最大公因数。
  1. 这个题比 3164 更难想到一点点,主要难度在于提前储存 k 一共有哪些因子(同样的按一对一对的存储)
  1. 然后遍历该列表的时候,也有一个非常重要的点,即遍历到某一个点的时候,把这个点之前的所有满足条件的 cnt 的值加到 ans 上,然后再更新 cnt 中的因子数量。
  1. cnt 统计 nums[j] 前面每个数的每个因子的出现次数(即 nums[i] 中有多少个数包含某个因子),这样对于一个固定的 nums[j],符合条件的 nums[i] 的个数就是 cnt[k/gcd(k,nums[j])]
 
  • 作者:Lishen Qu
  • 链接:https://qulishen.top/article/leetcode-2183
  • 声明:本文采用 CC BY-NC-SA 4.0 许可协议,转载请注明出处。
相关文章
Leetcode-3164
Leetcode-3164Ubuntu 18.04 LTS 升级到 20.04 LTS
Loading...
目录
0%
题目描述代码理解
Lishen Qu
Lishen Qu
代码承愿
文章
7
分类
3
标签
4
最新发布
CVPR 2025 Highlight
CVPR 2025 Highlight
2025-5-7
ECCV 2024
ECCV 2024
2025-5-7
Ubuntu 18.04 LTS 升级到 20.04 LTS
Ubuntu 18.04 LTS 升级到 20.04 LTS
2025-4-5
Burst Image Restoration
Burst Image Restoration
2024-12-17
奇异值分解
奇异值分解
2024-12-17
Leetcode-3164
Leetcode-3164
2024-11-19
公告
😀 A papers was accepted and selected as highlight in CVPR 2025.
 
目录
0%
题目描述代码理解
2021-2025Lishen Qu.

Lishen Qu的博客 | 代码承愿

Powered byNotionNext 4.7.9.