【日常学习】【数学-其他】洛谷1403 约数研究题解

青旅半醒 2022-08-04 08:49 125阅读 0赞

于是又要迎来洛谷那凌然无言以对的题目摘要= =

# 洛谷1403 约数研究 #

本题地址：[ http://www.luogu.org/problem/show?pid=1403][http_www.luogu.org_problem_show_pid_1403]

## 题目描述 ##

科学家们在Samuel星球上的探险得到了丰富的能源储备，这使得空间站中大型计算机“Samuel2”的长时间运算成为了可能。由于在去年一年的辛苦工作取得了不错的成绩，小联允许用“Samuel2”进行数学研究。  
小联最近在研究和约数有关的问题，他统计每个正数N的约数的个数，并以f(N)来表示。现在小联希望用“Samuel2”来统计f(1)到f(N)的累加和M。  
f(n)表示n的约数个数，现在给出n，要求求出f(1)到f(n)的总和。

## 输入输出格式 ##

输入格式：

输入一行，一个整数n

输出格式：

输出一个整数，表示总和

## 输入输出样例 ##

输入样例\#1：

输出样例\#1：

## 说明 ##

【数据范围】  
20%N<=5000  
100%N<=1000000

这道题直接枚举每个数的因数一定是超时的

我们不妨这样想：对于n=10，10以内的数中，因数包括1的有10/1个，包括2的有10/2个，包括3得有10/3个……

以此类推，只要按照这个规律累加即可

代码：

#include
       
            
    using namespace std;    
    int main()    
    {    
        int n,i,s=0;    
        cin>>n;    
        for(i=1;i<=n;i++)    
            s+=n/i;    
        cout<

`这就完了吗？还能更优吗？我们应该去思考更快的方法，不断追求更优是人类进步的源泉（严肃脸）。 里奥神犇给出的是另一种做法，更加高效省时，那就是数形结合。 考虑n的因数，我们画一条xy=n的双曲线，那么双曲线上所有整数点的横坐标即为n的整数因数。 由于双曲线的对称性（即以y=x为轴对称），我们如果只考虑一半，这一半曲线的横纵整数坐标即为n的因数。 对于<n的整数，其双曲线在xy=n下面。对于sigma（1-n的因数），实际上是覆盖了xy=n下面这一片面积所有的整数点。因此，我们只需要求出xy=n一半面积覆盖的整数点再乘2即可。注意，直线y=x上的点需要特殊处理。 我们枚举i从1到根号n，即双曲线被y=x分开的上面一半的所有横坐标，那么每个横坐标对应的点的个数为[n/i]-i+1 其中[n/i]表示n/i向下取整，也就是这一列双曲线下面的整数点数，而减去的i则是对称轴y=x下面的点。对称轴上的点最后乘二时算了两次，最后还要减去。 引用一下里奥神犇的代码 #include <cstdio>   #include <algorithm>  //copyright by t14t41t #define ll long long   using namespace std;   const int a[6] = {0, 1, 3, 5, 8, 10};   ll f(int m)   {       if(m <= 5) return a[m];       ll sum = 0;       int i;       for(i = 1; i * i <= m; ++i)       {           sum += m / i - i + 1;       }       return ((sum << 1) - i + 1);   }   int main()   {       int n;       scanf("%d", &n);       printf("%lld\n", f(n));       return 0;   }  至此，本题完美解决 我觉得我也该整理一下博客分类了 ——岁暮阴阳催短景，天涯霜雪霁寒宵`

[http_www.luogu.org_problem_show_pid_1403]: http://www.luogu.org/problem/show?pid=1403