题解 P1403 【[AHOI2005]约数研究】
引领天下
2017-07-11 15:49:30
看到题解基本上都是数学方法，我就来个不一样的思路吧（说白了就是暴力）
首先，我们看一下数学方法的思路：
- 数学方法：
重点在于一个公式：
$$f(i)=\frac{n}{i}$$
至于公式的含义，看我解释：
$1\sim n$ 的因子个数，可以看成含有 $2$ 这个因子的数的个数 $+$ 含有 $3$ 这个因子的数的个数 $+\dots+$ 含有 $n$ 这个因子的数的个数。
在 $1\sim n$ 中含有“2”这个因子的数有 $\frac{n}2$ 个，3 有 $\frac{n}3$ 个，以此类推，公式就出来了。
数学方法代码：
```cpp
#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;
}
```
- 非数学方法：
概括起来就俩字：**暴力**！
但是纯暴力是绝对超时的，这题要是暴力不想超时的话，就得借用筛法的思想：
```cpp
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。
最后 `s+=a[i];` 累加所有 $a[i]$，由于此时已经更新过 $a[i]$ 了，可以放心加。
$i$ 这个循环跑了一遍后，$s$ 就是总的因子个数了。
非数学方法代码：
```cpp
#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;
}
```