← 完整题目索引

PROJECT EULER · #0609

π 序列

π Sequences

仅题目 · 已解决原题 ↗

对于每个 n≥1,质数计数函数 π(n) 等于质数数量 不超过n。
例如π(6)=3 和 π(100)=25。

我们说整数序列 u=(u0,⋯,um) 是一个 π 序列 如果

  • un≥1 适用于每个 n
  • un+1=π(un)
  • u 有两个或多个元件

对于 u0=10,存在三种不同的 π 序列:(10,4)、(10,4,2) 和 (10,4,2,1)。

令 c(u) 为 u 中非质数元素的数量。
令 p(n,k) 为 π 序列 u 的数量,其中 u0≤n 和 c(u)=k。
令P(n)为所有大于0的p(n,k)的乘积。
您将获得:P(10)=3×8×9×3=648 和 P(100)=31038676032。

查找 P(108)。以 1000000007 为模给出答案。

题解待补充

这道题的题目已收录,解题思路、代码和答案将在后续补充。