当前位置:网站首页>AcWing 179. Factorial decomposition problem solution
AcWing 179. Factorial decomposition problem solution
2022-07-06 11:16:00 【Octopus loving monster】
AcWing 197. Factorial decomposition Answer key
List of articles
Title Description
Given integer N N N , Try factorial N ! N! N! Decomposing prime factor , According to the form of the basic theorem of arithmetic, output the p i p_i pi and c i c_i ci that will do
Input format
An integer N N N
Output format
N ! N! N! The result of decomposing the prime factor , There are several lines , Each row of a pair of p i , c i p_i,c_i pi,ci , Means to contain p i c I p_i^{c_I} picI term . according to p i p_i pi Sequential output from small to large
Data range
3 ≤ N ≤ 1 0 6 3 \le N \le 10^6 3≤N≤106
Answer key
about N ! N! N! The quality factor of , We can judge , The maximum quality factor does not exceed N N N
prove :
Through the basic theorem of arithmetic
For any positive integer, there are
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
among P i P_i Pi by x x x The quality factor of
about 1 1 1 ~ N N N Each integer of can be decomposed into the form of basic theorem of arithmetic
therefore N ! N! N! The basic theorem of arithmetic is the former N N N The product of the basic arithmetic theorem of numbers , There is no more than N N N The quality factor of
Obtain evidence
So we just need to sift out 1 1 1~ N N N The prime number of
First, use the linear sieve to screen out the prime numbers
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;
}
}
}
After sifting the prime number
We calculate the order of each prime
Computation 1 1 1 ~ N N N How many numbers in have prime numbers p p p
Easy to get N / P N/P N/P Numbers have prime numbers p, These numbers are p Multiple , So these numbers have factors p p p
According to N / P 2 N/P^2 N/P2 The number contains factors p 2 p^2 p2
By analogy , We can calculate when N / P k N/P^k N/Pk When is 0, Prime number P P P The corresponding maximum order is k k k
The code for calculating the order is as follows
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);
}
Complete code
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);
}
}
}
边栏推荐
- Neo4j installation tutorial
- Software testing - interview question sharing
- MySQL主从复制、读写分离
- MySQL主從複制、讀寫分離
- Installation and use of MySQL under MySQL 19 Linux
- 自动机器学习框架介绍与使用(flaml、h2o)
- Install mongdb tutorial and redis tutorial under Windows
- 软件测试与质量学习笔记3--白盒测试
- Remember a company interview question: merge ordered arrays
- Install mysql5.5 and mysql8.0 under windows at the same time
猜你喜欢
Solution: log4j:warn please initialize the log4j system properly
Error connecting to MySQL database: 2059 - authentication plugin 'caching_ sha2_ The solution of 'password'
Why is MySQL still slow to query when indexing is used?
QT creator create button
Postman uses scripts to modify the values of environment variables
CSDN blog summary (I) -- a simple first edition implementation
Deoldify project problem - omp:error 15:initializing libiomp5md dll,but found libiomp5md. dll already initialized.
Did you forget to register or load this tag 报错解决方法
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
Did you forget to register or load this tag
随机推荐
【博主推荐】SSM框架的后台管理系统(附源码)
CSDN question and answer module Title Recommendation task (II) -- effect optimization
Cookie setting three-day secret free login (run tutorial)
JDBC原理
Error connecting to MySQL database: 2059 - authentication plugin 'caching_ sha2_ The solution of 'password'
Ansible实战系列三 _ task常用命令
Software testing - interview question sharing
[download app for free]ineukernel OCR image data recognition and acquisition principle and product application
Deoldify project problem - omp:error 15:initializing libiomp5md dll,but found libiomp5md. dll already initialized.
Why is MySQL still slow to query when indexing is used?
Postman uses scripts to modify the values of environment variables
02-项目实战之后台员工信息管理
报错解决 —— io.UnsupportedOperation: can‘t do nonzero end-relative seeks
Number game
连接MySQL数据库出现错误:2059 - authentication plugin ‘caching_sha2_password‘的解决方法
解决安装Failed building wheel for pillow
JDBC原理
CSDN question and answer tag skill tree (II) -- effect optimization
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
Basic use of redis