Difference between revisions of "Project Euler"
Xiejiadong (talk | contribs) |
Xiejiadong (talk | contribs) |
||
Line 70: | Line 70: | ||
答案:1739023853137。 | 答案:1739023853137。 | ||
+ | |||
+ | ==Problem 501== | ||
+ | ===Eight Divisors=== | ||
+ | Solved by Weaver_zhu | ||
+ | |||
+ | 题意:求$10^{12}$以内因子个数恰好为8的数的个数。 | ||
+ | 题意:分解素因子,分为一个素数的七次方,两个素数其中一个三次方和另一个相乘,三个不同素数相乘三种情况。学到一个新姿势Lehmer,0.5s求$\Pi(n),n<=10^{11}$,很强大。剩下的就是枚举较小的素数了。三个不同情况看起来是$n^2$的,但是枚举较小的两个加特判条件跳出循环其实会很快。最后程序运行9s。 | ||
+ | 答案:197912312715 | ||
==Problem 601== | ==Problem 601== | ||
+ | ===Divisibility streaks=== | ||
Solved by Weaver_zhu | Solved by Weaver_zhu | ||
Line 79: | Line 88: | ||
答案:1617243 | 答案:1617243 | ||
− | |||
− | |||
− | |||
− | |||
− | |||
− | |||
− |
Revision as of 15:03, 26 December 2018
挖了一个大坑,天知道什么时候能填完。感觉是不可能填完的。
Problem 1
Multiples of 3 and 5
Solved by Xiejiadong & Czarina.
题意:$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 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,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), i<=1<k$ 而 $(n+k)\nmid(k+1)$定义$P(s,N)$为$streak(i)=s, 1<i<N$的$i$的个数。求$\sum_{i=1}^{31}{i, 4^i}$
题解:列出同余方程,很像CRT但是模数互不相同。用exgcd使两两方程合并到一个同余方程,然后再逐个判断是否$(n+k)\nmid(k+1)$。因为1到31不互素很多所以就算是合并了31个方程模数也不会爆long long。枚举长度为一个很大的模数的时候逐个枚举是可以接受的。
答案:1617243