Difference between revisions of "Project Euler"

Revision as of 06:34, 22 December 2018

挖了一个大坑，天知道什么时候能填完。感觉是不可能填完的。

Solved by Xiejiadong & Czarina.

题意：$1000$以下约数包含$3$和$5$的数和。

题解：直接暴力/等差数列求和。

答案：233168。

Solved by Xiejiadong.

题意：求$10^6$以下循环串组成的数都是质数的数的个数。

题解：先把质数用筛选法筛出来，然后暴力枚举判断，时间复杂度$O(6*10^6)$。

答案：55。

Solved by Xiejiadong.

题意：求$10^6$以下满足十进制和二进制都是回文数的所有数和。

题解：枚举二进制的长度，dfs暴力所有的二进制数，再判断十进制数是否符合题意。

为了防止重复，我们要在制定二进制的长度以后，默认第一位必须是$1$。

这样做的复杂度会比直接判断的小一些。

答案：872187。

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。

@@ Line 55: / Line 55: @@
 有一个情况是，我们假设$x/y=z$，那么$y\times z=x$，$y+\frac{x}{y}=\frac{x}{z}+z$
-这样，我们可以假设$y<z$，也就是说，枚举的时候只需要枚举到$\sqrt(x)$即可。
+这样，我们可以假设$y<z$，也就是说，枚举的时候只需要枚举到$\sqrt{x}$即可。
 看起来复杂度是$O(n\sqrt{n})$，实际上，因为约数的关系，判断失败直接 break ，这样的时间复杂度是非常接近$O(nlogn)$的，很快就出解了。
 答案：1739023853137。