【欧拉计划】42. Coded triangle numbers

(取 $n$ 为单词数量,$m$ 为所有单词对应数值的最大值)

【思路】我们在 Problem 22 中使用了文件输入索引,同时对其进行操作。这次我们直接将索引每十个元素空一行,并存放于数组中。

接着我们只需要枚举每个单词并判断它所对应的数值是否为三角形数即可。

判断是否为三角形数可以采用二分法,单次时间复杂度为 $\mathcal O(\log \sqrt m)$

总体时间复杂度为 $\mathcal O(n \log \sqrt m)$:

阅读更多

【欧拉计划】41. Pandigital prime

(本题取 $n=9$)

【思路】$\mathcal O(n!)$ 构造全排列并判断是否为质数。由于 $n$ 较大,因此不宜使用欧拉筛。程序的时间复杂度为 $\mathcal O(n!10^{\frac{n}{2}})$:

阅读更多

【欧拉计划】39. Integer right triangles

(本题取 $n=1000$)

【思路】最外层枚举 $p$ 的值,里面两层枚举 $a,b$,从而计算得到是否有符合的 $c$。时间复杂度为 $\mathcal O(n^3)$:

阅读更多

【欧拉计划】37. Truncatable primes

(本题取 $n=1000000$)

【思路】$\mathcal O(n)$ 欧拉筛,然后枚举所有在范围内质数并检查是否符合题意。程序的时间复杂度为 $\mathcal O(n \log_{10} n)$:

阅读更多

【欧拉计划】36. Double-base palindromes

(本题取 $n=1000000$)

【思路】我们可以 $\mathcal O(n)$ 枚举所有在范围的整数,然后每次 $\mathcal O(\log n)$ 进行数位的处理和检查。总体时间复杂度为 $\mathcal O(n \log n)$:

阅读更多

【欧拉计划】34. Digit factorials

(本题取 $n=9$)

【思路】我们可以储存 $0 \sim 9$ 的所有阶乘的值,然后在 $[10,9!]$ 内枚举所有的数并检验即可。枚举的时间复杂度为 $\mathcal O(n!)$:

阅读更多