题解 | #约数个数的和#

题目描述:给个n，求1到n的所有数的约数个数的和;

输入描述:一行一个正整数n,n <= 100000000

输出描述:输出一个整数，表示答案;

解析:

首先我们可以知道这是一道简单的数学题,考察我们对n个数约数的求解. 我们知道对于单个数n,它的约数可以进行组合.即1和n为一组, 2和n/2为一组(前提条件为n/2为整数), 3和n/3为一组(前提条件为n/2为整数)...n^1/2和n^1/2为一组(前提条件为n^1/2为整数),所以单个数约数的求解时间复杂度可以缩短为O(n^1/2). 此时,如果按照这种求解约数的方法进行求解,对1~n每个数进行遍历,则其时间复杂度为O(n^3/2). 显然,对于n <= 100000000这个数据范围肯定会超出时间限制,因此此种方法不可取. 那么要用什么方法进行求解呢? 接下来就会用到一个十分重要的解决问题的思想--逆向思维;

对于一个数 i,我们要在1~ n个数中求有哪几个数的约数包含i,即求1~ n个数中有多少个数是 i的倍数. 我们可以用sum(i)来表示1~n中 i 的倍数的个数, 即有多少个数的约数中含有i;

则1到n的所有数的约数个数的和sum=sum(1)+sum(2)+...+sum(n)

代码如下:

#include<bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d\n",x)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
typedef long long ll;
const int mod = 1e9+7;

int main()
{
    ll n;
    while(~scanf("%lld",&n)){
        ll sum=0;
        for(int i=1;i<=n;i++){ //遍历n次,每一次遍历求出n个数中有多少个i的倍数
            sum+=n/i; 
        }
        printf("%lld\n",sum);
    }
  
}

这样子我们就把时间复杂度降低到了O(n)级, 但其实对于上面所写的代码还可以进行细微的修改,使得其效率更高;那么要如何进行修改呢?对于上面的数据进行分析,我们不难发现: 当i > n/2 时,1~n中i 的倍数就只有一个,因此我们无需对1 ~n个数进行全部遍历,只需对前n/2进行遍历即可

优化代码如下:

#include<bits/stdc++.h>
using namespace std;
#define sc(x) scanf("%d",&x)
#define pr(x) printf("%d\n",x)
#define rep(i, l, r) for (int i = (l); i <= (r); i++)
typedef long long ll;
const int mod = 1e9+7;

int main()
{
    ll n;
    while(~scanf("%lld",&n)){
        ll sum=n-(n/2);  //当i>=(n/2)时,其倍数就只有自己本身一个,因此无需遍历,直接进行计算
        for(int i=1;i<=n/2;i++){ //遍历n/2次,每一次遍历求出n个数中有多少个i的倍数
            sum+=n/i;  
        }
        printf("%lld\n",sum);
    }

}

写在最后:虽然这是一道简单的数学题,但其中体现了逆向思维的重要性. 在算法竞赛中,题目千奇百怪,题目求解的正确与否其实并不是特别重要.其中蕴含的解决问题的思维方法才是重中之重.进行算法的学习,重点不在于刷题,做题,而在于学习其中的方法精髓.只有学好了这些,我们才能在算法竞赛中脱颖而出 ,而那些优质的思维方法不仅仅有助于我们学习竞赛,在日常生活,它也能很好的帮助我们解决实际问题,拓宽思维,从不同的角度去寻找解决问题的方法

以上就是我对这个问题的全部看法,由于能力问题,其中或许有许多不足之处,还望各位大佬能提出指正