如果有一个正整数N,能被2520整除,则N就是完美数。 现有一个非常大的正整数M,最高位为1,其余均为0,请计算在[1,M][1,M]范围内有多少个完美数。
时间: 2024-06-07 15:11:41 浏览: 163
首先我们需要知道什么是2520。2520是一个小于等于10的正整数的最小公倍数,也就是说,如果一个正整数能够被2、3、4、5、6、7、8、9、10整除,那么它一定能够被2520整除。
因此,我们可以分别计算在[1, M]范围内能够被2、3、4、5、6、7、8、9、10整除的数的个数,然后用容斥原理求出既能被这些数整除又能被2520整除的数的个数。
具体地,设$f_i$为在[1, M]范围内能够被$i$整除的数的个数,那么$f_2 = \lfloor \frac{M}{2} \rfloor$,$f_3 = \lfloor \frac{M}{3} \rfloor$,$f_4 = \lfloor \frac{M}{4} \rfloor$,$f_5 = \lfloor \frac{M}{5} \rfloor$,$f_6 = \lfloor \frac{M}{6} \rfloor$,$f_7 = \lfloor \frac{M}{7} \rfloor$,$f_8 = \lfloor \frac{M}{8} \rfloor$,$f_9 = \lfloor \frac{M}{9} \rfloor$,$f_{10} = \lfloor \frac{M}{10} \rfloor$。
然后,设$g_i$为在[1, M]范围内能够被$i$和2520同时整除的数的个数,那么容斥原理告诉我们,既能被2、3、4、5、6、7、8、9、10整除又能被2520整除的数的个数为:
$$g_2 - g_3 + g_4 - g_5 + g_6 - g_7 + g_8 - g_9 + g_{10}$$
接下来,我们需要计算$g_i$。设$h_i$为在[1, M/2520]范围内能够被$i$整除的数的个数,那么有:
$$g_i = f_{2520i} - h_i$$
其中$f_{2520i}$表示在[1, M]范围内能够被2520$i$整除的数的个数,即$\lfloor \frac{M}{2520i} \rfloor$。
因此,我们可以用前缀和来快速计算$f$和$h$,然后套用上面的公式计算$g$,最后用容斥原理求出答案即可。
时间复杂度为$O(1)$。
阅读全文