Project Euler 581
题目
-smooth triangular numbers
A number is -smooth if it has
no prime factors larger than .
Let be the sequence of
triangular numbers, ie .
Find the sum of all indices
such that is -smooth.
Størmer 定理
Størmer 定理,说明了上述定义的全体 -smooth 数(注意这里的 是一个质数集合,比小于等于 的全体质数这种集合更普遍)中,连续两个数 都是 -smooth 数的 的数量是有限的,并提供了一个算法查找这些 :
假设集合 的大小为 ,其中最大的质数为 .
那么枚举由集合 中的质因子组合而成的所有无平方因子数 (一共有 个这样的 ),然后解以下佩尔方程:
那么,对这个佩尔方程的前 个解 一一进行测试。如果 都是 -smooth 的,那么就找到了一个 -smooth 对。
注意当 时,佩尔方程无解,因此需要规避这种情况。
解决方案
如果一个三角形数 是 -smooth 的,那么说明 和 是 -smooth 的。
一开始的想法则是通过深度优先搜索直接产生所有 -smooth 数 ,并判断 是否为 -smooth 数。并且拟定一个枚举上限 。
之后,我查阅了 Størmer 定理并直接解决本问题,至于佩尔方程的解法在 66 题已经详述。
不过,让我比较惊讶的是,Størmer 定理的实现效率会比直接搜索更低。
OEIS 上的数列 A002072 则给出了最大答案的上限。在 FORMULA
一栏中,找到
1
| a(n) < 10^n/n except for n=4. (Conjectured, from experimental data.) - M. F. Hasler, Jan 16 2015
|
在实现 Størmer 定理时,还顺带了这个条件进行剪枝。
由于实现 Størmer 定理的效率过低,此处不附上使用它实现的代码。
代码
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31
| # include <bits/stdc++.h> using namespace std; typedef long long ll; const int M=47; ll MX; int pr[M+4],m=0,b[M+4]; ll ans=0; void dfs(int f,ll x){ if(f==m+1){ ll y=x+1; for(int i=1;i<=m&&y>1;i++) while(y%pr[i]==0) y/=pr[i]; if(y==1) ans+=x; return; } for(;x<=MX;x*=pr[f]) dfs(f+1,x); } int main(){ for(int i=2;i<=M;i++){ if(b[i]) continue; pr[++m]=i; for(int j=i+i;j<=M;j+=i) b[j]=1; } MX=(m==4?4374:pow(10,m)/m); dfs(1,1); printf("%lld\n",ans); }
|