牛牛的“质因数”（欧拉筛）

差一点过掉的数论题emmmm,比赛时思路对了，但是拼接时应该用快速幂和一个数组记录位数，而不是转换成字符串拼接再转换回去，也算学到了一点经验
题目：https://ac.nowcoder.com/acm/problem/217840
思路：每次用最小质因子更新，比如12=223,就欧拉筛记录一下最小质因子，因为质因子分解的第一个数必然是最小质因子，如dp[12]=dp[2]*dp[12/2],这个乘法就是两个数拼接的部分，用数组deg记录每个数的位数，快速幂qpow(10,deg[i/vis[i]]),再乘加一下，就实现了。

#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn=4e6+5;
const int mod=1e9+7;
int dp[maxn];
int prime[maxn];
int deg[maxn];
int vis[maxn];
int cnt;
int n;
ll qpow(ll a,ll x)
{
    ll res=1;
    ll b=x;
    while(b)
    {
        if(b&1) res=res*a%mod;
        a=a*a%mod;
        b>>=1;
    }
    return res%mod;
}
void del()
{
    vis[0]=1;
    vis[1]=1;
    for(int i=2;i<=maxn;i++)
    {
        if(vis[i]==0)
        {
            prime[cnt++]=i;
        }
        for(int j=0;j<cnt&&(i*prime[j]<=maxn);j++)
        {
            vis[i*prime[j]]=prime[j];
            if(i%prime[j]==0) break;
        }
    }
}
int sol()
{
    int res=0;
    for(int i=2;i<=n;i++)
    {
        if(!vis[i])
        {
            int x=i;
            int cnt=0;
            while(x)
            {
                x/=10;
                cnt++;
            }
            deg[i]=cnt;
            dp[i]=i;
            res=(res+dp[i])%mod;
        }
        else{
            dp[i]=((dp[vis[i]]*qpow(10ll,deg[i/vis[i]]))%mod+dp[i/vis[i]])%mod;
            deg[i]=deg[vis[i]]+deg[i/vis[i]];
            res=(res+dp[i])%mod;
        }
    }
    return res%mod;
}
int main()
{
    del();
    scanf("%d",&n);
    int res=sol();
    printf("%d\n",res);
    return 0;
}