Project Euler 212

来源: 康MM 于 2008-10-11 17:04:48 [档案] [博客] [旧帖] [给我悄悄话] 本文已被阅读：次 (771 bytes)

用 { (x0,y0,z0), (dx,dy,dz) } 表示长方体 { (X,Y,Z) : x0 ≤ X ≤ x0+dx, y0 ≤ Y ≤ y0+dy, z0 ≤ Z ≤ z0+dz }。

令 C1,...,C50000 为如下定义的 50000 个长方体：

x0 = S(6n-5) modulo 10000
y0 = S(6n-4) modulo 10000
z0 = S(6n-3) modulo 10000
dx = 1 + (S(6n-2) modulo 399)
dy = 1 + (S(6n-1) modulo 399)
dz = 1 + (S(6n) modulo 399)

其中 S(1),...,S(300000) 是所谓 "延迟 Fibonacci 数列":

对 1 ≤ k ≤ 55, S(k) = [100003 - 200003k + 300007k^3] (modulo 1000000)。对 56 > k, S(k) = [S(k-24) + S(k-55)] (modulo 1000000)。

例如 C1 是 {(7,53,183),(94,369,56)}, C2 是 {(2383,3563,5079),(42,212,344)}, ...。

前 100 个长方体的并集的体积是 723581599。

求所有 50000 个长方体 C1,...,C50000 的并集的体积。