Difference between revisions of "Project Euler"

From EOJ Wiki
Jump to navigation Jump to search
 
(22 intermediate revisions by the same user not shown)
Line 7: Line 7:
 
Solved by Xiejiadong.
 
Solved by Xiejiadong.
  
题意:一千以下约数包含$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