A. 求 1 - N 每个数的约数集合
求 1 - N 每个数字约数集合，显然用试除法不合适，在这里用倍数法。对于每个数字找到范围内它的倍数，则这个倍数就可以标记约数了。
但是这是 syoj，作为一个成熟的 oier，你要学会**高效输出**，指本题卡 scanf，需要优化输出，否则你只能得到 40pts 的好成绩。
对了今天的又一经验教训：最好别用 define int long long，最好别乱开 long long，否则你会变得不幸。
```cpp
#include<bits/stdc++.h>
using namespace std;
const int N = 1e6 + 10;
int n;
vector<int> ys[N];
int main()
{
scanf("%d", &n);
for(int i = 1; i <= n; i ++ )
for(int j = 1; j <= n / i; j ++ ) ys[i * j].push_back(i);
for(int i = 1; i <= n; i ++ )
{
for(int j = 0; j < ys[i].size(); j ++ ) printf("%d ", ys[i][j]);
puts("");
}
}
```
B.求 N 的约数的个数、所有约数的和。
本题数据比较水所以就偷了个懒：用试除法暴力求约数。复杂度 $O(\sqrt{N})$。
```cpp
#include<bits/stdc++.h>
#define ll long long
using namespace std;
const int N = 1e7 + 10;
int tot;
ll n, ans;
ll ys[N];
int main()
{
scanf("%lld", &n);
for(int i = 1; i <= n / i; i ++ )
{
if(n % i == 0)
{
ys[++ tot] = i;
if(n / i != i) ys[++ tot] = n / i;
}
}
for(int i = 1; i <= tot; i ++ ) ans += ys[i];
printf("%lld\n%lld", tot, ans);
}
```
C.求 1 ~ N 每个数的约数个数之和
如果你还像 B 一样试除法，你会得到 40pts 的好成绩；
如果你发现：对于约数 i，1 - N 中共有 $\lfloor n / i \rfloor$ 个约数，那么容易得到式子：$ ans = \sum _ {i = 1} ^ n \lfloor n / i \rfloor$
据此，你可以 $O(n)$ 求解该问题，能得到 60pts 的好成绩。
此时，通过打表，我们发现还可以优化。可以发现 $\lfloor n / i \rfloor$ 有很多都是一样的，于是累计过程中可以找出来相同的一段一起加：`(n / (n / i) - i + 1) * (n / i)`。复杂度 $O(2 \sqrt{N})$ 。
```cpp
#include<cstdio>
#define int long long
int n, ans;
signed main()
{
scanf("%lld",&n);
for(int i = 1, j; i <= n; i = j + 1)
{
j = n / (n / i);
ans += (n / i) * (j - i + 1);
}
printf("%lld", ans);
}
```
以及，在洛谷题解里看到说本题还可以 $O(n ^ \frac{1} {3}$ $log$ $n)$ 解决，不过那就是黑题了。[指路](https://www.luogu.com.cn/problem/SP26073)
[洛谷本题弱化版](https://www.luogu.com.cn/problem/P1403)