当前位置:网站首页>AcWing 179.阶乘分解 题解
AcWing 179.阶乘分解 题解
2022-07-06 09:14:00 【爱吃章鱼的怪兽】
AcWing 197. 阶乘分解 题解
题目描述
给定整数 N N N , 试把阶乘 N ! N! N! 分解质因数,按照算术基本定理的形式输出分解结果中的 p i p_i pi和 c i c_i ci即可
输入格式
一个整数 N N N
输出格式
N ! N! N! 分解质因数后的结果,共若干行,每行一对 p i , c i p_i,c_i pi,ci ,表示含有 p i c I p_i^{c_I} picI项。按照 p i p_i pi 从小到大的顺序输出
数据范围
3 ≤ N ≤ 1 0 6 3 \le N \le 10^6 3≤N≤106
题解
对于 N ! N! N! 的质因子,我们可以判断,最大的质因子不超过 N N N
证明:
通过算数基本定理
对于任意正整数有
x = p 1 α 1 ⋅ p 2 α 2 ⋅ p 3 α 3 … ⋅ p n α n x=p_1^{\alpha_1} · p_2^{\alpha_2}·p_3^{\alpha_3}\dots·p_n^{\alpha_n} x=p1α1⋅p2α2⋅p3α3…⋅pnαn
其中 P i P_i Pi 为 x x x 的质因子
对于 1 1 1 ~ N N N 的每个整数都可以分解成如算数基本定理的形式
因此 N ! N! N! 的算数基本定理为前 N N N 个数的算术基本定理的乘积,其中不存在超过 N N N 的质因子
得证
因此我们只需要筛出 1 1 1~ N N 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 1 1 ~ N N N 中有多少个数有质数 p p p
易得有 N / P N/P N/P个数有质数p,这些数是p的倍数,因此这些数有因子 p p p
又根据 N / P 2 N/P^2 N/P2个数中含有因子 p 2 p^2 p2
依次类推,我们可以计算出当 N / P k N/P^k N/Pk时为0,即质数 P P P对应的最大阶数为 k k 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);
}
}
}
边栏推荐
- 安全测试涉及的测试对象
- Postman uses scripts to modify the values of environment variables
- A brief introduction to the microservice technology stack, the introduction and use of Eureka and ribbon
- 报错解决 —— io.UnsupportedOperation: can‘t do nonzero end-relative seeks
- Data dictionary in C #
- 安装numpy问题总结
- 图像识别问题 — pytesseract.TesseractNotFoundError: tesseract is not installed or it‘s not in your path
- MySQL主从复制、读写分离
- TCP/IP协议(UDP)
- Armv8-a programming guide MMU (2)
猜你喜欢
Install mongdb tutorial and redis tutorial under Windows
Postman Interface Association
Valentine's Day is coming, are you still worried about eating dog food? Teach you to make a confession wall hand in hand. Express your love to the person you want
[Thesis Writing] how to write function description of jsp online examination system
Unable to call numpy in pycharm, with an error modulenotfounderror: no module named 'numpy‘
CSDN blog summary (I) -- a simple first edition implementation
CSDN question and answer module Title Recommendation task (I) -- Construction of basic framework
MySQL主从复制、读写分离
02-项目实战之后台员工信息管理
QT creator specify editor settings
随机推荐
Ansible实战系列一 _ 入门
Basic use of redis
Some problems in the development of unity3d upgraded 2020 VR
安全测试涉及的测试对象
Install mongdb tutorial and redis tutorial under Windows
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
[C language foundation] 04 judgment and circulation
CSDN markdown editor
MySQL的一些随笔记录
Postman Interface Association
CSDN问答模块标题推荐任务(二) —— 效果优化
Copy constructor template and copy assignment operator template
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
MySQL flush operation
QT creator specify editor settings
Navicat 導出錶生成PDM文件
01项目需求分析 (点餐系统)
Timestamp with implicit default value is deprecated error in MySQL 5.6
Windows cannot start the MySQL service (located on the local computer) error 1067 the process terminated unexpectedly
CSDN-NLP:基于技能树和弱监督学习的博文难度等级分类 (一)