题目如下:
![](https://img.laitimes.com/img/9ZDMuAjOiMmIsIjOiQnIsISPrdEZwZ1Rh5WNXp1bwNjW1ZUba9VZwlHdsATOfd3bkFGazxCMx8VesATMfhHLlN3XnxCMwEzX0xiRGZkRGZ0Xy9GbvNGLpZTY1EmMZVDUSFTU4VFRR9Fd4VGdsYTMfVmepNHLrJXYtJXZ0F2dvwVZnFWbp1zczV2YvJHctM3cv1Ce-cmbw5yYhVGZ0E2YxMTMmJDNmZDZ4kTMwAzM5EmMlNDZjFjYy8CX0AzLchDMxIDMy8CXn9Gbi9CXzV2Zh1WavwVbvNmLvR3YxUjL1M3Lc9CX6MHc0RHaiojIsJye.png)
解题思路:因为n的最大值是1e8,所以暴力计算是不行的。首先,我们可以排除掉素数,因为素数的整数因子只有1和自己本身,所以累加的和肯定是1。对于非素数,我们首先找到它的最小整数因子,例如28,最小整数因子是2,表示[2,14]是其中一对整数因子;接下来对较大的那个整数因子继续做最小整数因子的分解,14表示成[2,7],再用上一次分解中较小的整数因子乘以本次分解中较小的整数因子,就是第二对整数因子,这里是[2*2,7],而后继续分解较大的整数因子,只到无法被分解为止(即这个数是素数为止)。到这里就可以得到这个整数的所有整数因子对,求和即可,注意不要忘了加上数字1。
代码如下: