Links: https://projecteuler.net/problem=401
这题是个比较经典的题，大概就是枚举$floor(n / i)$划分区间，然后复杂度就是$sqrt(n)$。直接用的scala的BigInt来做的话，需要花费1分钟，所以可以加上对中间值取模的优化，下面的代码运行时间大概10s。
Scala代码：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
32
33
34
35
36object PE401 {
val mod: Long = 1000000000L
def sum_square(n: Long): Long = {
var x: Long = n
var y: Long = n + 1
var z: Long = 2 * n + 1
if (x % 2 == 0)
x /= 2
else
y /= 2
if (x % 3 == 0)
x /= 3
else if (y % 3 == 0)
y /= 3
else
z /= 3
(((x % mod) * (y % mod) % mod) * (z % mod)) % mod
}
def main(args: Array[String]): Unit ={
var ans: Long = 0
val end: Long = 1000000000000000L
var idx: Long = 1
while (idx <= end) {
val mul: Long = end / idx
val next: Long = end / mul + 1
ans = (ans + (mul % mod * ((sum_square(next - 1) - sum_square(idx - 1) + mod) % mod)) % mod) % mod
idx = next
}
println(ans)
}
}
Answer: 281632621 (选中查看)