AcWing 179.阶乘分解 题解

AcWing 197. 阶乘分解 题解

更好的阅读体验

题目描述

给定整数 $N$ , 试把阶乘 $N!$ 分解质因数,按照算术基本定理的形式输出分解结果中的 $p_i$和$c_i$即可

输入格式

一个整数 $N$

输出格式

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

数据范围

$3\le N\le 10^6$

题解

对于 $N!$ 的质因子，我们可以判断，最大的质因子不超过 $N$

证明：

通过算数基本定理

对于任意正整数有
$$x=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\cdot p_3^{{\alpha }_3}\dots \cdot p_n^{{\alpha }_n}$$
其中$P_i$ 为 $x$ 的质因子

对于$1$ ~ $N$ 的每个整数都可以分解成如算数基本定理的形式

因此 $N!$ 的算数基本定理为前$N$ 个数的算术基本定理的乘积，其中不存在超过$N$ 的质因子

得证

因此我们只需要筛出$1$~ $N$ 的质数即可

首先利用线性筛筛出其中的质数

 public static void init(int n)
    {
    
        Arrays.fill(isPrime,true);
        for(int i=2;i<=n;i++)
        {
    
            if(isPrime[i])
                Primes[cnt++]=i;
            for(int j=0;j<cnt;j++)
            {
    
                int p=Primes[j];
                if(p*i>n)
                    break;
                isPrime[p*i]=false;
                if(i%p==0)
                    break;
            }
        }
    }

筛得质数后

我们计算每个质数的阶数

即计算 $1$ ~ $N$ 中有多少个数有质数 $p$

易得有 $N/P$个数有质数p，这些数是p的倍数，因此这些数有因子$p$

又根据$N/P^2$个数中含有因子$p^2$

依次类推，我们可以计算出当$N/P^k$时为0，即质数$P$对应的最大阶数为$k$

计算阶数的代码如下

 for(int i=0;i<cnt;i++)
        {
    
            int res=0;
            int p=Primes[i];
            int tmp=n;
            while(tmp>0)
            {
    
                res+=tmp/p;
                tmp/=p;
            }
            System.out.println(Primes[i]+" "+res);
        }

完整代码

import java.io.*;
import java.util.*;

public class Main{
    
    static int n;
    static final int N=(int)1e6+10;
    static boolean[] isPrime=new boolean[N];
    static int[] Primes=new int[N];
    static int cnt=0;
    public static void  init(int n)
    {
    
        Arrays.fill(isPrime,true);
        for(int i=2;i<=n;i++)
        {
    
            if(isPrime[i])
                Primes[cnt++]=i;
            for(int j=0;j<cnt;j++)
            {
    
                int p=Primes[j];
                if(p*i>n)
                    break;
                isPrime[p*i]=false;
                if(i%p==0)
                    break;
            }
        }
    }
    public static void main(String[] agrs) throws IOException
    {
    
        BufferedReader reader=new BufferedReader(new InputStreamReader(System.in));
        n=Integer.parseInt(reader.readLine());
        init(n);
        for(int i=0;i<cnt;i++)
        {
    
            int res=0;
            int p=Primes[i];
            int tmp=n;
            while(tmp>0)
            {
    
                res+=tmp/p;
                tmp/=p;
            }
            System.out.println(Primes[i]+" "+res);
        }
    }
}