用欧拉计划学Rust编程语言(第700题:Eulercoin)
问题描述:
欧拉诞生于1707年4月15日,对于序列(1504170715041707 * n) mod 4503599627370517,如果一个元素小于前面发现的所有Eulercoin,则其称为Eulercoin。
例如,第一个元素是1504170715041707,为第一个Eulercoin,第二个元素为3008341430083414,由于它大于1504170715041707,所以不是Eulercoin。然而,第三个元素为8912517754604,比前面的数都小,被称为Eulercoin。前两个Eulercoins之和是1513083232796311。
求所有Eulercoin之和。
解题过程:
第一步,先根据题意暴力求解
这个代码非常容易写出来。
const INC: u64 = 1504170715041707_u64; const MOD: u64 = 4503599627370517_u64; let mut x = 0_u64; let mut min = INC; for n in 1_u64.. { x = (x + INC) % MOD; if x <= min { min = x; println!("{:20} {:20}", n, x); } }
运行这个程序,可以输出如下结果。
1504170715041707 8912517754604 2044785486369 1311409677241 578033868113 422691927098 267349986083 112008045068 68674149121 25340253174 7346610401 4046188430 745766459 428410324 111054189 15806432 15397267 14988102 14578937 14169772 13760607 13351442 12942277 12533112 12123947 11714782 11305617 10896452 10487287 10078122 9668957 9259792 8850627 8441462 8032297 7623132 7213967 6804802 6395637 5986472 5577307 5168142 4758977 4349812 3940647 3531482 3122317 2713152 2303987 1894822 1485657 1076492 667327 258162 … … … … … … … …
越往后,想找到一个Eulercoin愈发困难,必须得改进算法。
第二步,找规律
在n=2527之后,后一个eulercoin与前一个eulercoin有着递推的关系,补上一些数字之后,就能发现更为明显的关系。比如,n=2021, 6569, 30824, 116727…时,得到的数虽然不是eulercoin,但数值非常大,与4503599627370517越来越接近。
根据发现的规律,需要保存好最小的数和最大的数,不用一个数一个数的计算,效率非常高,不到1秒计算完成。
let mut sum = 1504170715041707_u64 + 8912517754604_u64 + 2044785486369_u64 + 1311409677241_u64; let mut n_max = 2021_u64; let mut max = 4502866251561389_u64; let mut n = 2527_u64; let mut x = 1311409677241_u64; let mut min = x; while min > 0 { let temp_n = n + n_max; let temp_x = (x + max) % 4503599627370517_u64; if temp_x <= min { n = temp_n; x = temp_x; min = x; sum += x; println!("{:20} {:12} {:20}", n, x, sum); } if temp_x > max { n_max = temp_n; max = temp_x; //println!("max: {} {} ", n_max, max); } }
?
再优化
看了欧拉论坛中的优秀贴子,发现n的索引值并不需要记录,代码还可以更优美一些。
let inc = 1504170715041707_u64; let modular = 4503599627370517_u64; let mut low = inc; let mut high = inc; let mut sum = inc; while low > 0 { let next = (low + high) % modular; if next < low { low = next; sum += low; println!("{:20} {:20}", low, sum); } else { high = next; } } println!("{}", sum);
相关推荐
zhangxiafll 2020-11-13
svap 2020-11-09
viplinux 2020-10-28
Justhavefun 2020-10-22
lousir 2020-10-21
longzhiwen 2020-10-16
Justhavefun 2020-09-25
归去来兮 2020-09-18
zhouxiaojie 2020-09-16
gamedevd 2020-09-04
tkernel 2020-09-03
Trustport 2020-09-01
svap 2020-08-25
tkernel 2020-08-18
lihn 2020-08-18
归去来兮 2020-07-28
TianlangStudio 2020-07-18
iammjun 2020-07-07
Colourful 2020-07-03