A. 求 1 - N 每个数的约数集合
求 1 - N 每个数字约数集合,显然用试除法不合适,在这里用倍数法。对于每个数字找到范围内它的倍数,则这个倍数就可以标记约数了。
但是这是 syoj,作为一个成熟的 oier,你要学会高效输出,指本题卡 scanf,需要优化输出,否则你只能得到 40pts 的好成绩。
对了今天的又一经验教训:最好别用 define int long long,最好别乱开 long long,否则你会变得不幸。
#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 的约数的个数、所有约数的和。
本题数据比较水所以就偷了个懒:用试除法暴力求约数。时间复杂度是 $\sqrt(N)$。
#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})$ 。
#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)$ 解决,不过那就是黑题了。指路
标签:约数,int,scanf,long,5.30,main,ll,模拟,小记 From: https://www.cnblogs.com/Moyyer-suiy/p/17444736.html