当前位置:网站首页>AcWing 1294. Cherry Blossom explanation
AcWing 1294. Cherry Blossom explanation
2022-07-06 11:16:00 【Octopus loving monster】
AcWing 1294. Cherry blossoms Answer key
Title Description
Given an integer n n n , Find how many positive integer pairs ( x , y ) (x,y) (x,y) Satisfy 1 x + 1 y = 1 n ! \dfrac{1}{x}+\dfrac{1}{y}=\dfrac{1}{n!} x1+y1=n!1
Input format :
An integer n n n
Output format :
An integer , Indicates the number of pairs that meet the conditions
The answer is right 1 0 9 + 7 10^9+7 109+7 modulus
Data range
1 ≤ n ≤ 1 0 6 1\le n \le 10^6 1≤n≤106
Answer key
Look at the formula , Easy to launch x > n ! x > n! x>n! y > n ! y >n! y>n!
Two unknowns x , y x,y x,y, Knowing one of them, you can launch another
So we might as well set y = n ! + k y=n!+k y=n!+k
The transformed formula is
1 x + 1 n ! + k = 1 n ! \dfrac{1}{x}+\dfrac{1}{n!+k}=\dfrac{1}{n!} x1+n!+k1=n!1
Divide the formula on both sides to get n ! ( n ! + k ) + ( n ! ) x = x ( n ! + k ) n!(n!+k)+(n!)x=x(n!+k) n!(n!+k)+(n!)x=x(n!+k)
Change can get
x = n ! ( n ! + k ) k = ( n ! ) 2 k + n ! x=\dfrac{n!(n!+k)}{k}=\dfrac{(n!)^2}{k}+n! x=kn!(n!+k)=k(n!)2+n!
because x To satisfy the property of positive integers , So the problem turns into k The value of needs to become ( n ! ) 2 (n!)^2 (n!)2 The divisor of
The problem became Find the divisor of a number
To find the divisor, you can use Basic theorem of arithmetic
The basic theorem of arithmetic is as follows
Any positive integer can be uniquely determined by its prime factor ( among p i p_i pi Is its qualitative factor )
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
According to the full arrangement formula, the number of factors is
( α 1 + 1 ) ⋅ ( α 2 + 1 ) ⋅ ( α 2 + 1 ) ⋅ ( α 2 + 1 ) (\alpha_1+1)·(\alpha_2+1)·(\alpha_2+1)·(\alpha_2+1) (α1+1)⋅(α2+1)⋅(α2+1)⋅(α2+1)
The problem becomes a solution ( n ! ) 2 (n!)^2 (n!)2 The prime factor of and the order of each prime factor
We can ask for ( n ! ) (n!) (n!) And the order of each prime factor, then multiply the order 2 You can get there ( n ! ) 2 (n!)^2 (n!)2 Solution
How to find ( n ! ) (n!) (n!) For the quality factor and the order of the quality factor, please refer to my other blog
AcWing 197. Factorial decomposition Answer key
Get ( n ! ) (n!) (n!) Multiply the order of the prime factor by 2, Finally, by using the calculation formula of the number of factors, we can get k All values of
For each of these k Each value has a x The value corresponds to , Then all the final values are the number of positive integer pairs
Complete code
import java.io.*;
import java.util.*;
public class Main {
static int n;
static final int N=1000010;
static final long MOD=1000000007;
static int[] Primes =new int[N];
static boolean[] isPrime =new boolean[N];
static int cnt=0;
static long ans=1;
public static void init(int n)// Linear sieve
{
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(i*p>n)
break;
isPrime[i*p]=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++)// Decomposing the prime factor
{
int tmp=n;
int p=Primes[i];
long res=0;
while(tmp>0)
{
res+=tmp/p;
tmp/=p;
}
res*=2;// The order of the prime factor converted to square
ans=(ans%MOD)*((res+1)%MOD);// Factor calculation formula
ans%=MOD;
}
System.out.println(ans);
}
}
边栏推荐
- Julia 1.6 1.7 common problem solving
- Summary of numpy installation problems
- MySQL主从复制、读写分离
- Postman environment variable settings
- Why is MySQL still slow to query when indexing is used?
- [Thesis Writing] how to write function description of jsp online examination system
- Invalid default value for 'create appears when importing SQL_ Time 'error reporting solution
- QT creator support platform
- Ubuntu 20.04 安装 MySQL
- [download app for free]ineukernel OCR image data recognition and acquisition principle and product application
猜你喜欢
机器学习笔记-Week02-卷积神经网络
1. Mx6u learning notes (VII): bare metal development (4) -- master frequency and clock configuration
Use dapr to shorten software development cycle and improve production efficiency
Csdn-nlp: difficulty level classification of blog posts based on skill tree and weak supervised learning (I)
PyCharm中无法调用numpy,报错ModuleNotFoundError: No module named ‘numpy‘
图片上色项目 —— Deoldify
02-项目实战之后台员工信息管理
Machine learning -- census data analysis
CSDN question and answer tag skill tree (I) -- Construction of basic framework
AcWing 1298.曹冲养猪 题解
随机推荐
02 staff information management after the actual project
[recommended by bloggers] background management system of SSM framework (with source code)
數據庫高級學習筆記--SQL語句
JDBC原理
MySQL other hosts cannot connect to the local database
The virtual machine Ping is connected to the host, and the host Ping is not connected to the virtual machine
Ansible实战系列三 _ task常用命令
TCP/IP协议(UDP)
QT creator shape
Postman uses scripts to modify the values of environment variables
Dotnet replaces asp Net core's underlying communication is the IPC Library of named pipes
安装numpy问题总结
Swagger、Yapi接口管理服务_SE
[recommended by bloggers] asp Net WebService background data API JSON (with source code)
Base de données Advanced Learning Notes - - SQL statements
C language advanced pointer Full Version (array pointer, pointer array discrimination, function pointer)
Postman Interface Association
CSDN blog summary (I) -- a simple first edition implementation
When you open the browser, you will also open mango TV, Tiktok and other websites outside the home page
[number theory] divisor