题解

看到质数有关的，先打一个欧拉筛上去。时间复杂度：$O(n)$.

这样我们得到了所有不超过 $n$ 的质数。数位分离一下，计算和并取模即可。

Code:

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const ll MAXN=2e5+25,MOD=1093;
ll n,ans,pcnt;
ll prm[MAXN];
bool isp[MAXN]={true,true};
int main(){
    cin>>n;
    for(ll i=2;i<=n;i++){
        if(!isp[i]) prm[++pcnt]=i;
        for(ll j=1;j<=pcnt;j++){
            if(i*prm[j]>n) break;
            isp[i*prm[j]]=true;
            if(i%prm[j]==0) break;
        }
    }
    for(ll i=1;i<=pcnt;i++){
        while(prm[i]){
            ans+=prm[i]%10;
            if(ans>=MOD) ans-=MOD;
            prm[i]/=10;
        }
    }
    cout<<ans;
    return 0;
}