【数论】阶乘分解

深碍√TFBOYSˉ_ 2024-03-26 18:25 68阅读 0赞

**今天过的非常bad，因为我发现前面有些数论题我还是没搞懂**

[197. 阶乘分解 - AcWing题库][197. _ - AcWing]

![76f6262c1a605625f4285a5194b43fd0.png][]

思路：

这道题，我们去**分类计算贡献**

贡献就是（每个质因子在式子里的个数+1）

把这个贡献乘起来，就是答案

我们去枚举质因子，然后对于每一个质因子，都去直接在1\*2\*3\*....\*n这个式子里面计算贡献

比如，对于质因子p，考虑p在式子里的贡献，p\*p在式子里的贡献，....

那么p在式子里面出现了n/p次，p\*p在式子里出现了n/(p\*p),....

因此就是这么写

Code：

#include <bits/stdc++.h>
    using namespace std;
    const int mxn=1e6+10;
    int n,len=0;
    int prime[mxn],vis[mxn];
    void init(int n){
        for(int i=2;i<=n;i++){
            if(!vis[i]) prime[++len]=i;
            for(int j=1;i*prime[j]<=n;j++){
                vis[i*prime[j]]=1;
                if(i%prime[j]==0) break;
            }
        }
    }
    int main(){
        ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
        cin>>n;
        init(n);
        for(int i=1;i<=len;i++){
            int p=prime[i];
            int res=0;
            for(int j=n;j;j/=p) res+=j/p;
            cout<<p<<" "<<res<<'\n';
        }
    }

[197. _ - AcWing]: https://www.acwing.com/problem/content/199/
[76f6262c1a605625f4285a5194b43fd0.png]: https://image.dandelioncloud.cn/pgy_files/images/2024/03/26/37a42a0df132416abc574d511b633125.png

发表评论取消回复

表情：

评论列表（有 0 条评论，68人围观）

还没有评论，来说两句吧...

相关阅读

相关数论4——快速乘（1.0模板）

一、普通乘法： **对于a\*n**：普通乘法本质： n个a相加； /*******普通乘法*****/ int ans; for...

我就是我/ 2024年04月17日 05:40/ 0 赞/ 81 阅读

相关【数论】阶乘分解

今天过的非常bad，因为我发现前面有些数论题我还是没搞懂 [197. 阶乘分解 - AcWing题库][197. _ - AcWing] ![76f6262c1a60562

深碍√TFBOYSˉ_/ 2024年03月26日 18:25/ 0 赞/ 69 阅读

相关阶乘

function fn(num) { return(function infn(num) { if (num <= 1

た入场券/ 2023年06月03日 15:59/ 0 赞/ 554 阅读

相关大数阶乘

描述我们都知道如何计算一个数的阶乘，可是，如果这个数很大呢，我们该如何去计算它并输出它？输入输入一个整数m(0<m<=5000) 输出输出m的阶乘，

男娘i/ 2022年08月02日 01:27/ 0 赞/ 455 阅读

相关（ACM数论）求N的阶乘末尾有多少个0

问题描述：给定一个整数N，那么N的阶乘N！末尾有多少个0？这个问题的难点在于，不能直接计算出N！，因为会溢出。既然不能直接计算，那就换个姿势计算（手动滑稽）首先，我

港控/mmm°/ 2022年07月17日 03:23/ 0 赞/ 233 阅读

相关阶乘

问题描述　　一个整数n的阶乘可以写成n!，它表示从1到n这n个整数的乘积。阶乘的增长速度非常快，例如，13!就已经比较大了，已经无法存放在一个整型变量中；而35!就更大了

雨点打透心脏的1/2处/ 2022年04月10日 06:42/ 0 赞/ 335 阅读

相关 197. 阶乘分解(素数筛)

[![知识共享许可协议][80x15.png]][80x15.png 1] 本作品采用[知识共享署名-相同方式共享 4.0 国际许可协议][80x15.png 1]进行许可

一时失言乱红尘/ 2021年10月29日 10:00/ 0 赞/ 387 阅读

相关阶乘和

阶乘和链接：http://ybt.ssoier.cn:8088/problem\_show.php?pid=1173 时间限制: 1000 ms

ゝ一纸荒年。/ 2021年09月29日 14:48/ 0 赞/ 430 阅读

相关阶乘

题目要求：使用while循环计算1+1/2！+1/3！+……+1/20！分析：我们可以观察到的现象：1、分子都为1；2、分母为阶乘表达式，已知阶乘表

墨蓝/ 2021年09月15日 23:14/ 0 赞/ 462 阅读

相关阶乘计算

蓝桥杯学习记录 ![在这里插入图片描述][watermark_type_ZmFuZ3poZW5naGVpdGk_shadow_10_text_aHR0cHM6Ly9ibG

一时失言乱红尘/ 2021年07月24日 16:23/ 0 赞/ 515 阅读