AcWing - 197 - 阶乘分解

2021-02-02 21:16

阅读：419

标签：print 因子 code ace amp 理论 main 需要因数分解

https://www.acwing.com/problem/content/199/

求解n!的质因数分解，n数量级1e6。

一个最简单的思路就是暴力分解每个数的质因数，复杂度过高。

换一种思路，当需要批量处理的时候，用线性筛求出每个数的最小质因数，然后对这个数进行质因数分解只需要log级别。

191ms：

#include
using namespace std;
typedef long long ll;

const int MAXN = 1e6;
int minp[MAXN + 5];
int p[MAXN + 5], ptop;
void sieve(int n) {
    minp[1] = 1;
    for(int i = 2; i  1) {
            ++cnt[minp[tmp]];
            tmp /= minp[tmp];
        }
    }

    for(int i = 2; i

还有另一种思路复杂度是一样的，但是不需要这么多除法。显然n以内拥有因子p的恰好有n/p个，而拥有两个因子p的恰好有n/(p^2)个，用乘法直接计算理论上更快。

43ms：

#include
using namespace std;
typedef long long ll;

const int MAXN = 1e6;
int p[MAXN + 5], ptop;
void sieve(int n) {
    for(int i = 2; i

AcWing - 197 - 阶乘分解

标签：print 因子 code ace amp 理论 main 需要因数分解

原文地址：https://www.cnblogs.com/Inko/p/11528776.html

上一篇：Windows 的 80 端口被 System 进程占用解决方案

下一篇：如何在Windows服务器上新建一个Powershell.ps1的定时任务

文章来自：搜素材网的编程语言模块，转载请注明文章出处。
文章标题：AcWing - 197 - 阶乘分解
文章链接：http://soscw.com/index.php/essay/50116.html

亲，登录后才可以留言！

AcWing - 197 - 阶乘分解

评论

热门文章

推荐文章

最新文章

置顶文章