AcWing 1294. Cherry Blossom explanation

AcWing 1294. Cherry blossoms Answer key

Better reading experience

Title Description

Given an integer $n$ , Find how many positive integer pairs $(x,y)$ Satisfy $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$

Input format ：

An integer $n$

Output format ：

An integer , Indicates the number of pairs that meet the conditions

The answer is right $10^9+7$ modulus

Data range

$1\le n\le 10^6$

Answer key

Look at the formula , Easy to launch $x>n!$$y>n!$

Two unknowns $x,y$, Knowing one of them, you can launch another

So we might as well set $y=n!+k$

The transformed formula is
$$\frac{1}{x}+\frac{1}{n!+k}=\frac{1}{n!}$$

Divide the formula on both sides to get $n!(n!+k)+(n!)x=x(n!+k)$

Change can get
$$x=\frac{n!(n!+k)}{k}=\frac{(n!{)}^2}{k}+n!$$
because x To satisfy the property of positive integers , So the problem turns into k The value of needs to become $(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$ Is its qualitative factor )
$$x=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\cdot p_3^{{\alpha }_3}\dots \cdot p_n^{{\alpha }_n}$$

According to the full arrangement formula, the number of factors is
$$({\alpha }_1+1)\cdot ({\alpha }_2+1)\cdot ({\alpha }_2+1)\cdot ({\alpha }_2+1)$$

The problem becomes a solution $(n!{)}^2$ The prime factor of and the order of each prime factor

We can ask for $(n!)$ And the order of each prime factor, then multiply the order 2 You can get there $(n!{)}^2$ Solution

How to find $(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!)$ 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);
    }
}