【调和级数】100321. 优质数对的总数 II

本文涉及知识点

调和级数
质数、最大公约数、菲蜀定理

LeetCode100321. 优质数对的总数 II

给你两个整数数组 nums1 和 nums2,长度分别为 n 和 m。同时给你一个正整数 k。
如果 nums1[i] 可以被 nums2[j] * k 整除,则称数对 (i, j) 为 优质数对(0 <= i <= n - 1, 0 <= j <= m - 1)。
返回 优质数对 的总数。
示例 1:
输入:nums1 = [1,3,4], nums2 = [1,3,4], k = 1
输出:5
解释:
5个优质数对分别是 (0, 0), (1, 0), (1, 1), (2, 0), 和 (2, 2)。
示例 2:
输入:nums1 = [1,2,4,12], nums2 = [2,4], k = 3
输出:2
解释:
2个优质数对分别是 (3, 0) 和 (3, 1)。
提示:
1 <= n, m <= 105
1 <= nums1[i], nums2[j] <= 106
1 <= k <= 103

调和级数

nums1中的元素如果不是k的倍数,删除。是k的倍数, /= k。
cnt1 记录nums1中各元素的数量。
令 max1 = (nums1)
∀ \forall n ∈ \in nums2。 如果n的m倍(m>0) 在nums1中存在,则是优质对。
如果n × \times ×m > max,则无需继续枚举m。
枚举1到y的不超过y的倍数,时间复杂度:y + y/2+y/3 ⋯ \cdots 1 就是调和级数,故时间复杂度是:O(ylogy)。
注意:如果nums2有重复元素,则时间复杂度是O(nn)。比如:全部是1。所以:必须用cnt2记录nums2各元素数量。

超时代码

class Solution {
public:long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {int iMax = *std::max_element(nums1.begin(), nums1.end());vector<int> vCnt1(iMax + 1);for (const auto& n : nums1) {if (0 != n % k) {continue;}vCnt1[n / k]++;}while (vCnt1.size() &&(vCnt1.back() == 0)) {vCnt1.pop_back();}iMax = vCnt1.size() - 1;long long llRet = 0;for (const auto& n : nums2) {for (int tmp = n; tmp <= iMax; tmp += n) {llRet += vCnt1[tmp];}}return llRet;}
};

代码

class Solution {
public:long long numberOfPairs(vector<int>& nums1, vector<int>& nums2, int k) {vector<int> tmp;for (const auto& n : nums1) {if (0 != n % k) { continue; }tmp.emplace_back(n/k);}if (tmp.empty()) { return 0; }int iMax = *std::max_element(tmp.begin(), tmp.end());vector<int> vCnt1(iMax + 1);for (auto& n : tmp) {vCnt1[n]++;}const int iMax2 = *std::max_element(nums2.begin(), nums2.end());vector<long long> vCnt2(iMax2+1);for (auto& n : nums2) {vCnt2[n]++;}long long llRet = 0;for (int i = 1; i <= iMax2; i++ ) {for (int tmp = i; tmp <= iMax; tmp += i) {llRet += vCnt1[tmp]*vCnt2[i];}}return llRet;}
};

扩展阅读

视频课程

有效学习:明确的目标 及时的反馈 拉伸区(难度合适),可以先学简单的课程,请移步CSDN学院,听白银讲师(也就是鄙人)的讲解。
https://edu.csdn.net/course/detail/38771

如何你想快速形成战斗了,为老板分忧,请学习C#入职培训、C++入职培训等课程
https://edu.csdn.net/lecturer/6176

相关下载

想高屋建瓴的学习算法,请下载《喜缺全书算法册》doc版
https://download.csdn.net/download/he_zhidan/88348653

我想对大家说的话
《喜缺全书算法册》以原理、正确性证明、总结为主。
闻缺陷则喜是一个美好的愿望,早发现问题,早修改问题,给老板节约钱。
子墨子言之:事无终始,无务多业。也就是我们常说的专业的人做专业的事。
如果程序是一条龙,那算法就是他的是睛

测试环境

操作系统:win7 开发环境: VS2019 C++17
或者 操作系统:win10 开发环境: VS2022 C++17
如无特殊说明,本算法用**C++**实现。

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/332026.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

手机版AI写作软件哪个好用?5款AI写作软件分享

在这个快节凑的时代&#xff0c;人们对于高效、便捷的创作方式很是追求。尤其是在人工智能技术发展迅速的今天&#xff0c;AI写作软件的出现&#xff0c;让很多自媒体创作者都会想到在手机上面进内容创作&#xff0c;这样不仅能提高工作效率&#xff0c;而且工作的自由度会更高…

ciscn2024(上传一下,有侵权什么的问题的话联系删除)

Web Simple_php 这个Simple_php一点儿也不Simple (⋟﹏⋞) 源码放这儿了&#xff1a; <?phpini_set(open_basedir, /var/www/html/); error_reporting(0);if(isset($_POST[cmd])){$cmd escapeshellcmd($_POST[cmd]); if (!preg_match(/ls|dir|nl|nc|cat|tail|more|flag…

Java中IO流类的体系

Java为我们提供了多种多样的IO流&#xff0c;我们可以根据不同的功能及性能要求挑选合适的IO流&#xff0c;如图所示&#xff0c;为Java中IO流类的体系。 从上图发现&#xff0c;很多流都是成对出现的&#xff0c;比如&#xff1a; FileInputStream/FileOutputStream&#xff0…

vue3的api风格

Vue的组件有两种不同的风格&#xff1a;组合式API 和 选项式API 选项式api 选项式API&#xff0c;可以用包含多个选项的对象来描述组件的逻辑&#xff0c;如&#xff1a;data&#xff0c;methods&#xff0c;mounted等。 组合式api setup&#xff1a;是一个标识&#xff0c;告…

【全开源】答题考试系统源码(FastAdmin+ThinkPHP+Uniapp)

答题考试系统源码&#xff1a;构建高效、安全的在线考试平台 引言 在当今数字化时代&#xff0c;在线考试系统已成为教育机构和企业选拔人才的重要工具。一个稳定、高效、安全的答题考试系统源码是构建这样平台的核心。本文将深入探讨答题考试系统源码的关键要素&#xff0c;…

民宿bug

前端 后端 1 订单管理 订单日期已过&#xff0c;状态没有变成已完成

window环境下QT5开发环境的搭建

1、安装visual Stusio 15 生成工具2012 2、安装Visual studio Enterprise 2017 3、Visual studio Enterprise 2017安装完成之后&#xff0c; 修改&#xff1a;选择桌面调试&#xff0c;如下&#xff1a; 4、打开QTcreator&#xff0c;选项中&#xff0c;配置编译器&#xff…

C++学习/复习5--构造函数与初始化/static成员/友元/内部类/匿名对象/编译器的拷贝构造优化

一、本章概要 二、再谈构造函数 1.构造体赋初值与初始化 2.初始化列表与初始化 2.1定义 2.2注意事项与举例 3.explicit关键字与构造函数 3.1隐式类型转换 也叫做自动类型转换 这种转换通常是从存储范围小的类型到存储范围大的类型&#xff0c;或者是从低精度的数值类型到高…

利用基于CNN的人员检测与关键词识别的TinyML实现无接触电梯

目录 说明 论文概述 摘要 引言 现有非接触式电梯解决方案 新解决方案的需求 tinyML实施 系统构建和算法管道 CNN和TinyML实现 结果与讨论 结论 视频演示和代码可用性 一点感想 说明 我一直使用Google Schloar订阅最新的论文消息&#xff0c;今天看到一篇论文的标…

租赁系统|北京租赁系统|租赁软件开发流程

在数字化时代的浪潮下&#xff0c;小程序成为了各行各业争相探索的新领域。租赁行业亦不例外&#xff0c;租赁小程序的开发不仅提升了用户体验&#xff0c;更为商家带来了更多商业机会。本文将详细解析租赁小程序的开发流程&#xff0c;为有志于进军小程序领域的租赁行业从业者…

【C语言】指针作为参数(传值调用vs传址调用)

前言 在前面讲了那些指针相关的内容后&#xff0c;是时候探讨一下指针有什么作用了。 在C语言中&#xff0c;指针有多种各不相同的应用&#xff0c;在本篇文章中&#xff0c;我们探讨一下指针作为函数参数的作用&#xff08;对比传值与传址两种不同函数调用方式&#xff09;。…

OS复习笔记ch6-1

死锁的原理 定义 一组进程中&#xff0c;其中每个进程因等待事件而阻塞&#xff0c;且所等待的事件只能被这组进程中的另一阻塞进程激发称之为死锁。 举例如下 四个车辆希望紧迫的希望能很快通过&#xff0c;每辆车需要两个象限的资源&#xff0c;然而四个车都只得到一个象…

【uni-best+UView】使用mitt实现自定义错误对话框

痛点 目前在设计一个uni-best的前端全局的异常提示信息&#xff0c;如果采用Toast方式&#xff0c;对微信支持的不友好。微信的7中文长度连个NPE信息都无法完整显示&#xff0c;更不用提Stacktrace的复杂报错了。如果使用对话框&#xff0c;必须在页面先预先定义&#xff0c;对…

嵌入式实时操作系统笔记3:FreeRTOS移植(STM32F407)_编写简单的FreeRTOS任务例程

上文讲到UC/OS III系统的移植&#xff0c;那篇文章是失败了的&#xff0c;网络上的资料真是层次不清&#xff0c;多有遗漏步骤&#xff0c;导致单片机连操作系统的初始化都卡在那&#xff0c;这次换个赛道&#xff0c;学FreeRTOS吧...... 今日任务如标题所示&#xff1a;FreeR…

手机端如何访问本地vue+vite项目,实现实时调试?

一、应用场景 h5&#xff08;vuevite&#xff09;嵌入app后&#xff0c;出现某种问题时&#xff0c;需要每次发布坏境后&#xff0c;才能才看效果&#xff0c;这种来回很耗时间&#xff0c;本文章在于解决手机端直接访问本地启动应用项目&#xff0c;无需重复发布坏境 二、实…

春秋CVE-2022-23906

简介 CMS Made Simple v2.2.15 被发现包含通过上传图片功能的远程命令执行 (RCE) 漏洞。此漏洞通过精心制作的图像文件被利用。 正文 1.进入靶场2.进入登录界面&#xff0c;弱口令admin/123456 3.进入后台&#xff0c;文件上传点 4.上传一句话木马图片 5.复制图片&#xf…

Mysql之主从同步

1.BinLog同步机制 Mysql要去保证高可用&#xff0c;或者去分担请求压力&#xff0c;一般会去主从部署&#xff0c;读写分离。写库只负责写&#xff0c;而读库更多的去承担读的请求&#xff0c;从库不写数据&#xff0c;数据从主库同步&#xff0c;那么到底是怎么同步的呢&…

嵌入式全栈开发学习笔记---C语言笔试复习大全23

目录 联合体 联合体的定义 联合体的长度 如果来判断设备的字节序&#xff1f; 如何把大端数据转换成小端数据&#xff1f; 枚举 枚举的定义 上一篇复习了结构体&#xff0c;这一节复习联合体和枚举。 说明&#xff1a;我们学过单片机的一般都是有C语言基础的了&#xff…

VBA技术资料MF157:创建每个标题的目录

我给VBA的定义&#xff1a;VBA是个人小型自动化处理的有效工具。利用好了&#xff0c;可以大大提高自己的工作效率&#xff0c;而且可以提高数据的准确度。“VBA语言専攻”提供的教程一共九套&#xff0c;分为初级、中级、高级三大部分&#xff0c;教程是对VBA的系统讲解&#…

一步到位:用Python实现PC屏幕截图并自动发送邮件,实现屏幕监控

在当前的数字化世界中&#xff0c;自动化已经成为我们日常生活和工作中的关键部分。它不仅提高了效率&#xff0c;还节省了大量的时间和精力。在这篇文章中&#xff0c;我们将探讨如何使用Python来实现一个特定的自动化任务 - PC屏幕截图自动发送到指定的邮箱。 这个任务可能看…