题解 P1403 【[AHOI2005]约数研究】

发表于 更新于 阅读次数： Waline：
P1403 【[AHOI2005]约数研究】题解。

看到一大堆人发数学方法的题解，我就来个不一样的思路吧（说白了就是暴力）

首先，我来说说数学方法的思路：

  • 数学方法思路：

其实，我一开始就是用数学方法过的，毕竟就8行代码

重点在于一个公式：

** f(i)=n/i **

至于公式是怎么推出来的，看我解释：

1-n的因子个数，可以看成共含有2因子的数的个数+含有3因子的数的个数……+含有n因子的数的个数

但在1~n中含有“2”这个因子的数有n/2个，3有n/3个，以此类推，公式就出来了

接下来就是代码了（我觉得代码就不用加注释了吧，第6行就是公式的循环写法）

  • 数学方法代码：
1
2
3
4
5
6
7
8
#include<iostream>
using namespace std;
int n,ans;
int main(void){
    cin>>n;
    for(int i=1;i<=n;i++)ans+=n/i;
    cout<<ans;
}
  • 非数学方法思路：

概括起来就俩字：# 暴力！

但是纯暴力是绝对超时的，这题要是暴力不想超时的话，就得用筛法

1
2
3
4
5
6
void H(){
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j+=i)a[j]++;
        s+=a[i];
    }
}

i就是循环的因子，从1到n，j是i的倍数，由于是从i开始的，所以a[i]本身也加了一次，既然是i的倍数，那么就含有i这个因子，加1。

最后

1
s+=a[i];

累加了a[i]，由于此时已经更新过a[i]了，可以放心加。

i这个循环跑了一遍后，s就是因子个数了

  • 非数学方法代码：
1
2
3
4
5
6
7
8
9
10
11
12
13
14
#include <cstdio>
int n,a[10000001],s;
void H(){//筛法函数，上面解释过了
    for (int i=1;i<=n;i++){
        for (int j=i;j<=n;j+=i)a[j]++;
        s+=a[i];
    }
}
int main(){
    scanf ("%d",&n);
    H();
    printf ("%d",s);//输出
    return 0;
}