Project Euler 603

题目

Substring sums of prime concatenations

Let \(S(n)\) be the sum of all contiguous integer-substrings that can be formed from the integer \(n\). The substrings need not be distinct.

For example, \(S(2024) = 2 + 0 + 2 + 4 + 20 + 02 + 24 + 202 + 024 + 2024 = 2304\).

Let \(P(n)\) be the integer formed by concatenating the first \(n\) primes together. For example, \(P(7) = 2357111317\).

Let \(C(n, k)\) be the integer formed by concatenating \(k\) copies of \(P(n)\) together. For example, \(C(7, 3) = 235711131723571113172357111317\).

Evaluate \(S(C(10^6, 10^{12})) \bmod (10^9 + 7)\).

解决方案

先考虑以线性时间计算\(S(n)\)。

将\(n\)看成是一个长度为\(m\)的字符串\(n=s_0s_1s_2\dots s_{m-1}s_m\)。考虑第\(i\)个字符\(s_i\)，它对答案\(S(n)\)的贡献值为\((i+1)\cdot s_i\cdot \dfrac{10^{m-i}-1}{9}\)。因为以\(s_i\)为结尾的字符串一共有\((i+1)\)个，以\(s_i\)为开头，\(s_j(i\le j< m)\)的字符串将会对答案贡献\(10^{j-i}\)。包含\(s_i\)的\((i+1)(n-i)\)个字符串对这两个步骤是独立的，因此最终答案为\(\displaystyle{S(n)=\sum_{i=0}^{m-1}(i+1)\cdot s_i\cdot\dfrac{10^{m-i}-1}{9}}\)。

对于一个长度为\(m\)的整数\(n\)被拼接\(k\)次后的整数\(n'\)，其长度为\(mk\)，并且有\(s'_i=s'_{i+m}=s'_{i+2m}=\dots=s'_{i+(k-1)m}\)。因此其结果为

\(\begin{aligned} &\sum_{i=0}^{m-1}\sum_{j=0}^{k-1}(i+jm+1)\cdot s_i\cdot \dfrac{10^{mk-(i+jm)}-1}{9}\\ =&\sum_{i=0}^{m-1} \dfrac{s_i}{9}\sum_{j=0}^{k-1}(i+jm+1)\cdot (10^{mk-(i+jm)}-1)\\ =&\sum_{i=0}^{m-1} \dfrac{s_i}{9}\left(-(i+1)k-\dfrac{(k-1)km}{2}+\sum_{j=0}^{k-1}(i+jm+1)\cdot 10^{mk-(i+jm)}\right)\\ =&\sum_{i=0}^{m-1} \dfrac{s_i}{9}\left(-(i+1)k-\dfrac{(k-1)km}{2}+\dfrac{10^{m-i} ((i+1)uv+m (v-ku))}{u^2}\right) \end{aligned}\)

其中\(u=10^m-1,v=10^{km}-1\)。

最终直接暴力计算出上面的求和式结果即可，前\(10^6\)个质数直接通过筛法获得。

代码

#include <bits/stdc++.h>
# include "tools.h"
using namespace std;
typedef long long ll;

const int N=1000000;
ll K=1e12;
ll mod=1e9+7;
vector<int>s;

int main(){
    int p=0;
    for(int i=0;i<N;i++){
        p=next_prime(p);
        int pre=s.size();
        for(int m=p;m;m/=10)
            s.push_back(m%10);
        reverse(s.begin()+pre,s.end());
    }
    int m=s.size();
    ll inv_2=mod_inverse(2,mod);
    ll inv_9=mod_inverse(9,mod);
    ll inv_10=mod_inverse(10,mod);
    ll pw10m=qpow(10,m,mod);
    ll u=(pw10m+mod-1)%mod;
    ll v=(qpow(pw10m,K,mod)+mod-1)%mod;
    ll inv_u2=mod_inverse(u*u%mod,mod);
    ll b=(K-1)%mod*(K%mod)%mod*m%mod*inv_2%mod;
    ll ans=0;
    for(ll i=0,t=pw10m;i<m;i++,t=t*inv_10%mod){
        ll a=K%mod*(i+1)%mod;
        ll c=t*((i+1)*u%mod*v%mod+m*(v-K%mod*u%mod+mod)%mod)%mod*inv_u2%mod;
        ans=(ans+inv_9*s[i]%mod*(c-a-b+mod+mod))%mod;
    }
    printf("%lld\n",ans);

}