牛客寒假集训营第二场I牛牛的“质因数”
前言
昨天是用分段打表过的,看了题解发现可以利用埃氏筛法,感觉还是有一定思维量的。
题目链接
题解
在埃氏筛法中,每个合数都有一个质数以及他的倍数筛出,也就是$vis[i*j]=1$,其中$i$是质数,$i\times j$自然是$i$的倍数。并且这里的$i$是从小到大枚举的,刚好符合题意。
当枚举到质因子$i$时,若$j$中还包含$k$个质因子$i$,那我们总共需要将$k+1$个$i$连接起来,也就是$dp[i\times j]=dp[i\times j]\times 10+i$,需要注意的是,这里的$\times 10$是针对个位数的质因子而言。比如$11$这种不止一位数的因子,我们需要$\times 100$。
代码
1 | /* |