C 数列之和
- 数列 $a$ 由 $10^{100}$ 项组成,从第一项开始有 $a_i = 2i - 2$。
- 将数列 $a$ 中所有长度大于 $1$ 的连续子数列的元素和去重后从小到大构成一个新的数列,求这个数列的第 $k$ 项。
注意到,答案为 $2(k + \lfloor \log_2{(k + \lfloor \log_2 k \rfloor)} \rfloor)$,时间复杂度 $\mathcal O(T)$。
- 数列 $a$ 由 $10^{100}$ 项组成,从第一项开始有 $a_i = 2i - 2$。
- 将数列 $a$ 中所有长度大于 $1$ 的连续子数列的元素和去重后从小到大构成一个新的数列,求这个数列的第 $k$ 项。
注意到,答案为 $2(k + \lfloor \log_2{(k + \lfloor \log_2 k \rfloor)} \rfloor)$,时间复杂度 $\mathcal O(T)$。
首先,需要特判 $c_i = c_j$ 但 $d_i \neq d_j$ 的情形,此时答案为 $0$。
否则,我们可以把每相邻的两条一元限制作为一个区间单独拎出来。这样做正确的原因是,每一个 $x_i$ 的取值只受前面一个数的影响。事实上,完全可以任意选取区间,只不过这样选可以利用已知的 $x_i$,依次讨论出 $a_{i+1}, b_{i+1}, a_{i+2}, b_{i+2}, \cdots$ 的可能取值,便于计算答案。
我们随便找几个数举个例子:
(本题取 $n=142857$)
【思路】从 $1$ 开始向更大的数进行枚举,利用 Python 整型字符串自由转换的功能进行判断,找到符合题意的数即可输出。
总体时间复杂度为 $\mathcal O(n)$:
【欧拉计划】51. Prime digit replacements
(本题取 $n=1000000$)
【思路】欧拉筛初始化后,对位数及空缺位置进行枚举,再分别判断 $0 \sim 9$ 填入之后是否为质数即可。
其中,在枚举方面,我们可以在 $0 \sim 9$ 之外新建一个特殊位 $10$,表示这个位置是待替换的。这样,我们的程序就无形之间被简化了。
总体时间复杂度为 $\mathcal O(n)$:
所有代码归档压缩包
完整版题解
1. Multiples of 3 and 5
2. Even Fibonacci numbers
3. Largest prime factor
4. Largest palindrome product
5. Smallest multiple
6. Sum square difference
7. 10001st prime
8. Largest product in a series
9. Special Pythagorean triplet
10. Summation of primes
11. Largest product in a grid
12. Highly divisible triangular number
13. Large sum
14. Longest Collatz sequence
15. Lattice paths
16. Power digit sum
17. Number letter counts
18. Maximum path sum I
19. Counting Sundays
20. Factorial digit sum
21. Amicable numbers
22. Names scores
23. Non-abundant sums
24. Lexicographic permutations
25. 1000-digit Fibonacci number
26. Reciprocal cycles
27. Quadratic primes
28. Number spiral diagonals
29. Distinct powers
30. Digit fifth powers
31. Coin sums
32. Pandigital products
33. Digit cancelling fractions
34. Digit factorials
35. Circular primes
36. Double-base palindromes
37. Truncatable primes
38. Pandigital multiples
39. Integer right triangles
40. Champernowne’s constant
41. Pandigital prime
42. Coded triangle numbers
43. Sub-string divisibility
44. Pentagon numbers
45. Triangular, pentagonal, and hexagonal
46. Goldbach’s other conjecture
47. Distinct primes factors
48. Self powers
49. Prime permutations
50. Consecutive prime sum
51. Prime digit replacements
52. Permuted multiples
(本题取 $n=1000$)
【思路】$\mathcal O(n)$ 枚举所有能被 $3$ 和被 $5$ 整除的数,最后把能被 $15$ 整除的数减掉:
【欧拉计划】50. Consecutive prime sum
(本题取 $n=1000000$,$m$ 为不超过 $n$ 的质数个数)
【思路】欧拉筛初始化后,采用前缀和预处理,一旦超过 $n$ 就不再继续做下去,这样会减小后续枚举范围。
紧接着在所有质数中枚举作为起始质数,然后取连续的 $maxl+1$ 个质数得到它们的和(规定 $maxl$ 为当前最多质数的个数),再判断是否为质数即可。
总体时间复杂度为 $\mathcal O(n+m^2)$:
【思路】先欧拉筛,然后枚举所有四位数的所有排列,最后去重后检验即可:
(本题取 $n=1000$,$m=10^{10}$)
【思路】Python
直接套 pow
: