Leetcode 1175:质数排列(超详细的解法!!!)
发布日期:2021-06-29 15:56:12
浏览次数:2
分类:技术文章
本文共 926 字,大约阅读时间需要 3 分钟。
请你帮忙给从 1
到 n
的数设计排列方案,使得所有的「质数」都应该被放在「质数索引」(索引从 1 开始)上;你需要返回可能的方案总数。
让我们一起来回顾一下「质数」:质数一定是大于 1 的,并且不能用两个小于它的正整数的乘积来表示。
由于答案可能会很大,所以请你返回答案 模 mod 10^9 + 7 之后的结果即可。
示例 1:
输入:n = 5输出:12解释:举个例子,[1,2,5,4,3] 是一个有效的排列,但 [5,2,3,4,1] 不是,因为在第二种情况里质数 5 被错误地放在索引为 1 的位置上。
示例 2:
输入:n = 100输出:682289015
提示:
1 <= n <= 100
解题思路
首先不难想到暴力解法,我们只要找到小于等于n
的质数有多少个(假设x
个),那么最后的结果就是x!*(n-x)!
个。
import mathclass Solution: def numPrimeArrangements(self, n: int) -> int: primes, st, cnt, MOD = [0]*(n + 1), [0]*(n + 1), 0, 10**9 + 7 for i in range(2, n + 1): if not st[i]: primes[cnt] = i cnt += 1 j = 0 while primes[j] <= n//i: st[primes[j] * i] = 1 if i % primes[j] == 0: break j += 1 return (math.factorial(cnt)%MOD * math.factorial(n - cnt)%MOD)%MOD
这个问题的考察点就是线性筛的知识。
我将该问题的其他语言版本添加到了我的
如有问题,希望大家指出!!!
转载地址:https://coordinate.blog.csdn.net/article/details/100528736 如侵犯您的版权,请留言回复原文章的地址,我们会给您删除此文章,给您带来不便请您谅解!
发表评论
最新留言
路过,博主的博客真漂亮。。
[***.116.15.85]2024年04月28日 06时46分39秒
关于作者
喝酒易醉,品茶养心,人生如梦,品茶悟道,何以解忧?唯有杜康!
-- 愿君每日到此一游!
推荐文章
树莓派“小霸王学习机”来了,一个自带键盘的电脑,售价不到500元
2019-04-29
H桥电机驱动电路详解
2019-04-29
电气毕业生在国家电网都干啥工作?
2019-04-29
为什么LED灯会越用越暗?
2019-04-29
知乎热议:嵌入式开发中C++好用吗?
2019-04-29
这100道Linux常见面试题,看看你会多少?
2019-04-29
嵌入式开发中常用的几种通信接口总结
2019-04-29
为什么你学C++这么难?
2019-04-29
无人机破巡检难题,秒变电网卫士
2019-04-29
五年,我成为了一名嵌入式工程师。
2019-04-29
2020年电赛题目,命题专家们怎么看?
2019-04-29
PCB元器件摆放不可忽略的10个技巧
2019-04-29
掌握AI核心技术没有秘籍,能自己创造就是王道
2019-04-29
大学老师的月薪多少?实话实说:4万多一点……
2019-04-29
2020年电赛题目,命题专家权威解析!
2019-04-29
写论文,这个神器不能少!
2019-04-29
现在做硬件工程师还有前途吗?
2019-04-29
华为被超越!这家公司成中国最大智能手机制造商,不是小米!
2019-04-29
芯片为什么持续缺货?
2019-04-29
美国无人机在火星首飞成功,创造历史,3米飞行高度悬停30秒
2019-04-29