本文共 957 字，大约阅读时间需要 3 分钟。

非常暴力的先筛一遍质数

然后对于$[2,n]$每个数分解质因子计算答案,$TLE$

想一下怎么来优化

我们发现,数字$i$的答案是有前驱的

形式化的说，设$i$的最小素因子是$k$

那么$i$最后的答案就相当于在$i/k$的答案前面拼上了一个$k$

那么就可以使用$dp$来求解了

#include 
   
    using namespace std;#define int long longconst int mod = 1e9+7;const int maxn = 1e7+10;int n,top,ans,vis[maxn],prime[maxn],mi[maxn],f[maxn],c[maxn],bit[maxn],len[maxn];int LEN(int x){
   	int now = 0;	while( x )	x/=10,now++;	return now;}void makeprime(){
   	for(int i=2;i<=n;i++)	{
   		if( !vis[i] )	prime[++top] = i,c[i] = LEN(i),mi[i] = i;		for(int j=1;j<=top&&i*prime[j]<=n;j++)		{
   			vis[i*prime[j]] = 1; mi[i*prime[j]] = prime[j];			if( i%prime[j]==0 )	break;		}	}}signed main(){
   	bit[0] = 1; for(int i=1;i<=70000;i++)	bit[i] = bit[i-1]*10%mod;	cin >> n;	makeprime();	for(int i=2;i<=n;i++)	{
   		int son = i/mi[i];		f[i] = ( f[son]+mi[i]*bit[len[son]]%mod )%mod;		len[i] = len[son]+c[mi[i]];		ans = ( ans+f[i] )%mod;	}	cout << ans;}
   

转载地址：https://issue-is-vegetable.blog.csdn.net/article/details/113618090 如侵犯您的版权，请留言回复原文章的地址，我们会给您删除此文章，给您带来不便请您谅解！