Project Euler 609

题目

$\pi$ sequences

For every $n \ge 1$ the prime-counting function $\pi(n)$ is equal to the number of primes not exceeding $n$.

E.g. $\pi(6)=3$ and $\pi(100)=25$.

We say that a sequence of integers $u = (u_0,\cdots,u_m)$ is a $\pi$ sequence if

• $u_n \ge 1$ for every $n$
• $u_{n+1}= \pi(u_n)$
• $u$ has two or more elements

For $u_0=10$ there are three distinct $\pi$ sequences: $(10,4), (10,4,2)$ and $(10,4,2,1)$.

Let $c(u)$ be the number of elements of $u$ that are not prime.

Let $p(n,k)$ be the number of $\pi$ sequences $u$ for which $u_0\le n$ and $c(u)=k$.

Let $P(n)$ be the product of all $p(n,k)$ that are larger than $0$.

You are given: $P(10)=3\times8\times9\times3=648$ and $P(100)=31038676032$.

Find $P(10^8)$. Give your answer modulo $1000000007$.

解决方案

利用线性筛生成所有质数，并直接计算出函数$\pi$的值。$u$序列直接通过迭代$\pi$值产生。

注意到，对于相邻两个质数$p,q$，发现$\pi(p)=\pi(p+1)=\pi(p+2)=\dots=\pi(q-1)$。因此，同时处理开头为$p\sim q-1$的$u$序列。

代码

#include <bits/stdc++.h>
typedef long long ll;
using namespace std;
const int N=100000000;
const int M=4*log2(N+4);
int s[N+4];
int v[N+4],pr[N+4],m=0;
int cnt[M+4];
ll mod=1e9+7;
int main(){
    for(int i=2;i<=N;i++){
        if(v[i]==0) v[i]=i,pr[++m]=i;
        for(int j=1;j<=m;j++){
            if(pr[j]>v[i]||pr[j]>N/i) break;
            v[i*pr[j]]=pr[j];
        }
        s[i]=s[i-1]+(v[i]==i);
    }
    for(int i=1;i<=m;i++){
        int l=pr[i],r=(i==m?N:pr[i+1]-1);
        int c=0;
        for(int j=s[l];j;j=s[j]){
            if(v[j]!=j) ++c;
            cnt[c+1]+=r-l;
            ++cnt[c];
            if(j==1) break;
        }
    }
    ll ans=1;
    for(int j=0;j<=M;j++)
        if(cnt[j]>0) ans=ans*cnt[j]%mod;
    printf("%lld\n",ans);
}