【欧拉计划】43. Sub-string divisibility
(本题取 $n=10$)
【思路】构造 $0 \sim 9$ 全排列,然后合成十位数后判断即可,时间复杂度为 $\mathcal O(n!10^{\frac{n}{2}})$:
(本题取 $n=10$)
【思路】构造 $0 \sim 9$ 全排列,然后合成十位数后判断即可,时间复杂度为 $\mathcal O(n!10^{\frac{n}{2}})$:
(取 $n$ 为单词数量,$m$ 为所有单词对应数值的最大值)
【思路】我们在 Problem 22 中使用了文件输入索引,同时对其进行操作。这次我们直接将索引每十个元素空一行,并存放于数组中。
接着我们只需要枚举每个单词并判断它所对应的数值是否为三角形数即可。
判断是否为三角形数可以采用二分法,单次时间复杂度为 $\mathcal O(\log \sqrt m)$
总体时间复杂度为 $\mathcal O(n \log \sqrt m)$:
(本题取 $n=9$)
【思路】$\mathcal O(n!)$ 构造全排列并判断是否为质数。由于 $n$ 较大,因此不宜使用欧拉筛。程序的时间复杂度为 $\mathcal O(n!10^{\frac{n}{2}})$:
【思路】由于一个整数 $x$ 的数位个数等于 $\log_{10} x+1$,因而我们可以不停累加,到了所需的值就进行计算:
(本题取 $n=1000$)
【思路】最外层枚举 $p$ 的值,里面两层枚举 $a,b$,从而计算得到是否有符合的 $c$。时间复杂度为 $\mathcal O(n^3)$:
【思路】暴力倒序枚举 $10000$ 以内的整数并检查:
(本题取 $n=1000000$)
【思路】$\mathcal O(n)$ 欧拉筛,然后枚举所有在范围内质数并检查是否符合题意。程序的时间复杂度为 $\mathcal O(n \log_{10} n)$:
(本题取 $n=1000000$)
【思路】我们可以 $\mathcal O(n)$ 枚举所有在范围的整数,然后每次 $\mathcal O(\log n)$ 进行数位的处理和检查。总体时间复杂度为 $\mathcal O(n \log n)$:
(本题取 $n=1000000$)
【思路】先 $\mathcal O(n)$ 欧拉筛,然后暴力枚举所有在范围内的质数:
(本题取 $n=9$)
【思路】我们可以储存 $0 \sim 9$ 的所有阶乘的值,然后在 $[10,9!]$ 内枚举所有的数并检验即可。枚举的时间复杂度为 $\mathcal O(n!)$: