Difference between revisions of "Project Euler"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
| (19 intermediate revisions by the same user not shown) | |||
| Line 5: | Line 5: | ||
=== Multiples of 3 and 5 === | === Multiples of 3 and 5 === | ||
| − | Solved by Xiejiadong | + | Solved by Xiejiadong. |
题意：$1000$以下约数包含$3$和$5$的数和。 | 题意：$1000$以下约数包含$3$和$5$的数和。 | ||
| Line 14: | Line 14: | ||
== Problem 2 == | == Problem 2 == | ||
| + | |||
| + | == Problem 35 == | ||
| + | |||
| + | === Circular primes === | ||
| + | |||
| + | Solved by Xiejiadong. | ||
| + | |||
| + | 题意：求$10^6$以下循环串组成的数都是质数的数的个数。 | ||
| + | |||
| + | 题解：先把质数用筛选法筛出来，然后暴力枚举判断，时间复杂度$O(6*10^6)$。 | ||
| + | |||
| + | 答案：55。 | ||
| + | |||
| + | == Problem 36 == | ||
| + | |||
| + | === Double-base palindromes === | ||
| + | |||
| + | Solved by Xiejiadong. | ||
| + | |||
| + | 题意：求$10^6$以下满足十进制和二进制都是回文数的所有数和。 | ||
| + | |||
| + | 题解：枚举二进制的长度，dfs暴力所有的二进制数，再判断十进制数是否符合题意。 | ||
| + | |||
| + | 为了防止重复，我们要在制定二进制的长度以后，默认第一位必须是$1$。 | ||
| + | |||
| + | 这样做的复杂度会比直接判断的小一些。 | ||
| + | |||
| + | 答案：872187。 | ||
| + | |||
| + | ==Problem 37== | ||
| + | ===Truncatable primes=== | ||
| + | Solved by Weaver_zhu | ||
| + | |||
| + | 题意：统计这样的数，从左到右去掉数字和从右往左去掉数字组成的新数都是素数。已知总共只有11个这样的数。 | ||
| + | |||
| + | 题解：这样的数不会太大，因为素数的分布越来越稀疏。筛一边1e7的素数发现已经有11个了。所以只需要线性筛+暴力判断。 | ||
| + | |||
| + | 答案：748317 | ||
| + | |||
| + | == Problem 151 == | ||
| + | |||
| + | === Paper sheets of standard sizes: an expected-value problem === | ||
| + | |||
| + | Solved by Weaver_zhu. | ||
| + | |||
| + | 题意：一开始有一张A1纸，每天需要使用一张A5纸，一共16天正好全部用完。每次随机选一张纸，如果比A5大，就一直对半剪最小的那一部分，直到剪出A5。如果拿到A5就不用剪。求只能拿出一张纸的情况的期望次数，除了第一天和最后一天的情况。 | ||
| + | |||
| + | 题解：直接概率dfs即可，这题竟然50% diffculty | ||
| + | |||
| + | 答案：0.464399。 | ||
| + | |||
| + | == Problem 152 == | ||
| + | |||
| + | === Writing 1/2 as a sum of inverse squares === | ||
| + | |||
| + | Solved by Weaver_zhu. | ||
| + | |||
| + | 题意：考虑2到80之间的整数，选取一些整数使得$ \sum_{i=1}^{k}{\frac{1}{a_i^2}} = \frac{1}{2}$，求有多少种不同的选取方法。比如有种方法：$\{2,3,4,6,7,9,12,15,28,30,35,36,45\}$ | ||
| + | |||
| + | 题解：考虑最后新加一个数$\frac{a}{b}+\frac{1}{x^2}$若b和x互质则新的分母将无法消掉x，这样就无法形成$\frac{1}{2}$。所以大于40的素数可以直接不予考虑。然而数还是很多，之后就是“毒瘤”般的一一检查消去规则。太小的素数还是交给暴搜，经手算（打表）可以发现11，17，23，29，31，37的倍数都不行，而(13,39,52)是唯一的消去方案。这样就只剩下30个左右的数，然后就是暴力了。 | ||
| + | |||
| + | 答案：301。 | ||
| + | |||
| + | == Problem 357 == | ||
| + | |||
| + | === Prime generating integers === | ||
| + | |||
| + | Solved by Xiejiadong. | ||
| + | |||
| + | 题意：求满足$x\le 10^8$且所有$x$的约数$y$满足$y+x/y$是质数的所有$x$的和。 | ||
| + | |||
| + | 题解：筛选法求质数，然后直接暴力判断，需要一些小优化。 | ||
| + | |||
| + | 有一个情况是，我们假设$x/y=z$，那么$y\times z=x$，$y+\frac{x}{y}=\frac{x}{z}+z$ | ||
| + | |||
| + | 这样，我们可以假设$y<z$，也就是说，枚举的时候只需要枚举到$\sqrt{x}$即可。 | ||
| + | |||
| + | 看起来复杂度是$O(n\sqrt{n})$，实际上，因为约数的关系，判断失败直接 break ，这样的时间复杂度是非常接近$O(nlogn)$的，很快就出解了。 | ||
| + | |||
| + | 答案：1739023853137。 | ||
| + | |||
| + | ==Problem 501== | ||
| + | ===Eight Divisors=== | ||
| + | Solved by Weaver_zhu | ||
| + | |||
| + | 题意：求$10^{12}$以内因子个数恰好为8的数的个数。 | ||
| + | |||
| + | 题意：分解素因子，分为一个素数的七次方，两个素数其中一个三次方和另一个相乘，三个不同素数相乘三种情况。学到一个新姿势Lehmer（其实是min25筛的一种），0.5s求$\Pi(n)，n<=10^{11}$，很强大。剩下的就是枚举较小的素数了。三个不同素数的情况看起来要$n^2$枚举，但是枚举较小的两个加特判条件跳出循环其实会很快。最后程序运行9s。 | ||
| + | |||
| + | 答案：197912312715 | ||
| + | |||
| + | ==Problem 601== | ||
| + | ===Divisibility streaks=== | ||
| + | Solved by Weaver_zhu | ||
| + | |||
| + | 题意：定义$streak(n)=k$ 其中 $(n+i)\mid(i+1), 1<=i<k$ 且 $(n+k)\not \mid(k+1)$定义$P(s,N)$为$streak(i)=s, 1<i<N$的$i$的个数。求$\sum_{i=1}^{31}{i, 4^i}$ | ||
| + | |||
| + | 题解：列出同余方程，很像CRT但是模数不是两两互素。用exgcd使两两方程合并到一个同余方程，然后再逐个判断是否$(n+k)\not \mid(k+1)$。因为1到31不互素很多所以就算是合并了31个方程模数也不会爆long long。枚举长度为一个很大的模数的时候逐个枚举是可以接受的。 | ||
| + | |||
| + | 答案：1617243 | ||
Latest revision as of 15:43, 17 April 2019
挖了一个大坑，天知道什么时候能填完。感觉是不可能填完的。
Problem 1
Multiples of 3 and 5
Solved by Xiejiadong.
题意：$1000$以下约数包含$3$和$5$的数和。
题解：直接暴力/等差数列求和。
答案：233168。
Problem 2
Problem 35
Circular primes
Solved by Xiejiadong.
题意：求$10^6$以下循环串组成的数都是质数的数的个数。
题解：先把质数用筛选法筛出来，然后暴力枚举判断，时间复杂度$O(6*10^6)$。
答案：55。
Problem 36
Double-base palindromes
Solved by Xiejiadong.
题意：求$10^6$以下满足十进制和二进制都是回文数的所有数和。
题解：枚举二进制的长度，dfs暴力所有的二进制数，再判断十进制数是否符合题意。
为了防止重复，我们要在制定二进制的长度以后，默认第一位必须是$1$。
这样做的复杂度会比直接判断的小一些。
答案：872187。
Problem 37
Truncatable primes
Solved by Weaver_zhu
题意：统计这样的数，从左到右去掉数字和从右往左去掉数字组成的新数都是素数。已知总共只有11个这样的数。
题解：这样的数不会太大，因为素数的分布越来越稀疏。筛一边1e7的素数发现已经有11个了。所以只需要线性筛+暴力判断。
答案：748317
Problem 151
Paper sheets of standard sizes: an expected-value problem
Solved by Weaver_zhu.
题意：一开始有一张A1纸，每天需要使用一张A5纸，一共16天正好全部用完。每次随机选一张纸，如果比A5大，就一直对半剪最小的那一部分，直到剪出A5。如果拿到A5就不用剪。求只能拿出一张纸的情况的期望次数，除了第一天和最后一天的情况。
题解：直接概率dfs即可，这题竟然50% diffculty
答案：0.464399。
Problem 152
Writing 1/2 as a sum of inverse squares
Solved by Weaver_zhu.
题意：考虑2到80之间的整数，选取一些整数使得$ \sum_{i=1}^{k}{\frac{1}{a_i^2}} = \frac{1}{2}$，求有多少种不同的选取方法。比如有种方法：$\{2,3,4,6,7,9,12,15,28,30,35,36,45\}$
题解：考虑最后新加一个数$\frac{a}{b}+\frac{1}{x^2}$若b和x互质则新的分母将无法消掉x，这样就无法形成$\frac{1}{2}$。所以大于40的素数可以直接不予考虑。然而数还是很多，之后就是“毒瘤”般的一一检查消去规则。太小的素数还是交给暴搜，经手算（打表）可以发现11，17，23，29，31，37的倍数都不行，而(13,39,52)是唯一的消去方案。这样就只剩下30个左右的数，然后就是暴力了。
答案：301。
Problem 357
Prime generating integers
Solved by Xiejiadong.
题意：求满足$x\le 10^8$且所有$x$的约数$y$满足$y+x/y$是质数的所有$x$的和。
题解：筛选法求质数，然后直接暴力判断，需要一些小优化。
有一个情况是，我们假设$x/y=z$，那么$y\times z=x$，$y+\frac{x}{y}=\frac{x}{z}+z$
这样，我们可以假设$y<z$，也就是说，枚举的时候只需要枚举到$\sqrt{x}$即可。
看起来复杂度是$O(n\sqrt{n})$，实际上，因为约数的关系，判断失败直接 break ，这样的时间复杂度是非常接近$O(nlogn)$的，很快就出解了。
答案：1739023853137。
Problem 501
Eight Divisors
Solved by Weaver_zhu
题意：求$10^{12}$以内因子个数恰好为8的数的个数。
题意：分解素因子，分为一个素数的七次方，两个素数其中一个三次方和另一个相乘，三个不同素数相乘三种情况。学到一个新姿势Lehmer（其实是min25筛的一种），0.5s求$\Pi(n)，n<=10^{11}$，很强大。剩下的就是枚举较小的素数了。三个不同素数的情况看起来要$n^2$枚举，但是枚举较小的两个加特判条件跳出循环其实会很快。最后程序运行9s。
答案：197912312715
Problem 601
Divisibility streaks
Solved by Weaver_zhu
题意：定义$streak(n)=k$ 其中 $(n+i)\mid(i+1), 1<=i<k$ 且 $(n+k)\not \mid(k+1)$定义$P(s,N)$为$streak(i)=s, 1<i<N$的$i$的个数。求$\sum_{i=1}^{31}{i, 4^i}$
题解：列出同余方程，很像CRT但是模数不是两两互素。用exgcd使两两方程合并到一个同余方程，然后再逐个判断是否$(n+k)\not \mid(k+1)$。因为1到31不互素很多所以就算是合并了31个方程模数也不会爆long long。枚举长度为一个很大的模数的时候逐个枚举是可以接受的。
答案：1617243