【欧拉计划】52. Permuted multiples
(本题取 $n=142857$)
【思路】从 $1$ 开始向更大的数进行枚举,利用 Python 整型字符串自由转换的功能进行判断,找到符合题意的数即可输出。
总体时间复杂度为 $\mathcal O(n)$:
(本题取 $n=142857$)
【思路】从 $1$ 开始向更大的数进行枚举,利用 Python 整型字符串自由转换的功能进行判断,找到符合题意的数即可输出。
总体时间复杂度为 $\mathcal O(n)$:
(本题取 $n=1000000$)
【思路】欧拉筛初始化后,对位数及空缺位置进行枚举,再分别判断 $0 \sim 9$ 填入之后是否为质数即可。
其中,在枚举方面,我们可以在 $0 \sim 9$ 之外新建一个特殊位 $10$,表示这个位置是待替换的。这样,我们的程序就无形之间被简化了。
总体时间复杂度为 $\mathcal O(n)$:
(本题取 $n=1000$)
【思路】$\mathcal O(n)$ 枚举所有能被 $3$ 和被 $5$ 整除的数,最后把能被 $15$ 整除的数减掉:
(本题取 $n=1000000$,$m$ 为不超过 $n$ 的质数个数)
【思路】欧拉筛初始化后,采用前缀和预处理,一旦超过 $n$ 就不再继续做下去,这样会减小后续枚举范围。
紧接着在所有质数中枚举作为起始质数,然后取连续的 $maxl+1$ 个质数得到它们的和(规定 $maxl$ 为当前最多质数的个数),再判断是否为质数即可。
总体时间复杂度为 $\mathcal O(n+m^2)$:
【思路】先欧拉筛,然后枚举所有四位数的所有排列,最后去重后检验即可:
(本题取 $n=1000$,$m=10^{10}$)
【思路】Python
直接套 pow
:
【思路】与 Problem 46 类似,我们先取一个足够大的上限 $n$,先欧拉筛得到质数表和合数表。
在判断合数是否有四个不同的质因数时,我们同样可以采取二分,找到不超过它的最大质数,然后倒着循环,统计出它的不同质因数个数即可。
总体时间复杂度为 $\mathcal O(n \log n)$:
【思路】取一个足够大的上限 $n$,确保最终答案不超过 $n$。我们可以采用欧拉筛得到所有的质数和合数表。注意合数不是按照顺序得到的,需要排序。
接着我们枚举所有在范围内的合数,二分找到不超过它的最大质数,然后判断二者之差是否能表示乘一个完全平方数的两倍即可。
总体时间复杂度为 $\mathcal O(n \log n)$:
【思路】不难发现三角形数必然是六边形数,因而我们可以从第 $144$ 项六边形数开始枚举,采用二分找到第一个既是五边形数又是六边形数的整数:
【思路】选定一个足够大的项数上限 $n$,然后 $\mathcal O(n^2)$ 枚举,判断的时候采用二分,总体时间复杂度为 $\mathcal O(n^2 \log n)$: