[LeetCode]周赛335 Problem 3-Solution_每日热点

2023-03-05 12:17:03 来源：哔哩哔哩

题目简述

给定一个长度为的序列，将其分为前后非空两段，使得前后两段的乘积互质，并输出分割点。如果分割点不存在，输出。

原题目链接：https://leetcode.cn/contest/weekly-contest-335/problems/split-the-array-to-make-coprime-products/

思路1

如果直接从左到右枚举分割点，并维护左右乘积，看似复杂度合理，但由于数值过大，必须使用高精度gcd，这样实际的复杂度（包括时间和编程难度）都很大。

(资料图片)

一般对于gcd，可以从因子来考虑。我们将中的所有数分解质因数，然后枚举分割点并维护左右乘积的分解结果就可以了。只要使用合理的维护技巧（见附录），复杂度可以做到。其中是筛素数的复杂度，。

由于质数数目的特性（），因此以内的素数数目也是万级别，因此也不妨尝试直接暴力维护乘积，复杂度为。如果不放心，可以使用bitset（比如我）优化到。

思路2（未验证）

在得到中的所有数的质因数分解后，从右到左枚举每一个数，与此同时维护当前每一个质因子在数组中出现的最小下标。这样我们可以得到对于每一个数而言，其后首个与它不互质的数的位置。这样，在之间不可能存在分割点。我们标记这整个区间内的位置为impossible。最后，枚举分割点，找到最小的非impossible的分割点即可。

注意到每次标记一个连续的区间，因此使用差分进行标记，复杂度为。

备注：当然，其实也没必要标记，可以直接根据一直往后“跳”就可以了。

附录

关于思路1中的维护策略。很简单，只需要考虑每一个数所涉及的个质因子即可。用一个cnt变量记录当前左右公共质因子数目，在更新中动态调整cnt。

后记

本来是想试一试leetcode的周赛如何，看看能不能二十分钟解决战斗。结果被T3安排了，写思路2WA傻了：

于是就有了这个solution，卧薪尝胆。复健是复健不了了，快乐竞赛。

代码比较简单就不给了。

关键词：就可以了从左到右可以使用

推荐内容

产业

游客因未购物遭导游辱骂？九寨沟：相关部门已介入调查

2021-10-20

油气

1

知识百科 e1是什么意思

2

百科深圳市宝安区财政局电话

3

河北深州警方打掉一暴力催债团伙 36名嫌犯被刑拘

4

寒潮降温破冰点如何保障温暖过冬？探访北京城管及供热

5

莆田致2死3伤案嫌犯拒捕并畏罪自杀经抢救无效死亡

6

福建福州一在建摩天轮发生垮塌事故原因正在调查中

7

为什么对张恒处3227万元罚款？其违法事实有哪些？

8

山西民政部门支出超2亿元捐款保障受灾困难民众基本生活

9

张恒被税务部门依法处以3227万元罚款

10

湖北赛武当国家级自然保护区监测到珍稀动物

经济

网络百科全书生平什么意思

1、生平释义：一个人生活的整个过程;一辈子。有生以来;平生。2、出自：清吴趼人《二十年目睹之怪现状》第二二回：那天凭空受了伯述的一席话

浙江杭州西湖首次推“环湖游线” 重现灵隐天竺上香水路

　　中新网杭州10月18日电 (王题题胡燕婕)云天收夏色，浅秋正渐浓。10月18日，浙江杭州市西湖游船有限公司推出的惠民多站点“西湖环湖游

税务机关处罚一名艺人经纪人

　　中国税务机关处罚一名艺人经纪人　　中新社北京10月18日电 (记者赵建华)上海市税务局第一稽查局前期在艺人郑爽偷逃税案件检查过程中

福建福州在建摩天轮事故续：安装过程中外围轮毂脱落无

　　中新网福州10月18日电 (记者龙敏王东明)福州市晋安区官方18日晚间通报，18日14时47分，晋安区岳峰镇化工路爱摩轮商业广场项目摩天

【母亲河畔的中国】黄河“润泽”甘肃：沿岸城市兴文旅

　　中新网兰州10月18日电 (闫姣艾庆龙吉翔)“红山白土头，黄河向西流。”不少人疑问，天下黄河向东流，为何甘肃永靖县这段黄河却向西