Acwing.197. 阶乘分解(题解)

2020-12-23 17:28

阅读：771

标签：flow org hid 结果 pre font 问题基本 atom

给定整数 N ，试把阶乘 N! 分解质因数，按照算术基本定理的形式输出分解结果中的 $p_{i}$ 和 $c_{i}$ 即可。

输入格式

一个整数N。

输出格式

N! 分解质因数后的结果，共若干行，每行一对 $p_{i}, c_{i}$ ，表示含有 $p_{i}^{c_{i}}$ 项。按照 $p_{i}$ 从小到大的顺序输出。

数据范围

$1 \leq N \leq 10^{6}$

输入样例：

输出样例：

2 3
3 1
5 1

样例解释

$5! = 120 = 2^{3} * 3 * 5$

水题，分解质因数，然后看到一个不一样的做法，是真的惊艳到我了，或许以后能够借鉴他的思路，换个角度思考问题。
思路，先用筛子筛出$10^6$内的素数，然后考虑$n$这个数，对于每个素数$x$而言，$n$是$x$的$n/x$倍，也就是说，对于小于等于$x$的数，形如$x,2x,3x...kx$这种形式有$\lfloor \frac{n}{x} \rfloor$个，那么很容易的得到，对于$x$而言，有$\lfloor \frac{n}{x} \rfloor$个数是$x$的倍数，即能被$x$整除；然后我们将$x*x$与上面的含义一样，意为计算$n$有几个$x*x$的倍数，这一步操作我们将$n/x$，含义一样。
$Code:$

#include 
using namespace std;
const int N = 1e6+10;
int n,prime[N],tot;
bool st[N];
void init(){
    for(int i=2;i=10000)continue;
            for(int j=i*i;j

Acwing.197. 阶乘分解(题解)

标签：flow org hid 结果 pre font 问题基本 atom

原文地址：https://www.cnblogs.com/violentbear/p/14157022.html

上一篇：Json，2020年api数据格式的Top 1

下一篇：这6本免费的书籍，助你“吃透”C#

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

亲，登录后才可以留言！

Acwing.197. 阶乘分解(题解)

输入格式

输出格式

数据范围

输入样例：

输出样例：

样例解释

评论

热门文章

推荐文章

最新文章

置顶文章