AcWing 1294.樱花 题解

更好的阅读体验

题目描述

给定一个整数 $n$ ,求有多少正整数对 $(x,y)$ 满足 $\frac{1}{x}+\frac{1}{y}=\frac{1}{n!}$

输入格式：

一个整数 $n$

输出格式：

一个整数，表示满足条件的数对数量

答案对$10^9+7$ 取模

数据范围

$1\le n\le 10^6$

题解

观察式子，容易推出 $x>n!$$y>n!$

两个未知量$x,y$, 知道其中一个后就能够推出另外一个

因此我们不妨设 $y=n!+k$

变换后的式子为
$$\frac{1}{x}+\frac{1}{n!+k}=\frac{1}{n!}$$

将式子两边通分可得 $n!(n!+k)+(n!)x=x(n!+k)$

变换可得
$$x=\frac{n!(n!+k)}{k}=\frac{(n!{)}^2}{k}+n!$$
由于x要满足正整数这一特性,所以问题转换成了k的值需要变成$(n!{)}^2$的约数

问题变成了求一个数的约数

求约数可以用 算数基本定理

算术基本定理如下

任何一个正整数都可以用它的质因子唯一确定(其中$p_i$为其质因子)
$$x=p_1^{{\alpha }_1}\cdot p_2^{{\alpha }_2}\cdot p_3^{{\alpha }_3}\dots \cdot p_n^{{\alpha }_n}$$

根据全排列公式则其因子个数为
$$({\alpha }_1+1)\cdot ({\alpha }_2+1)\cdot ({\alpha }_2+1)\cdot ({\alpha }_2+1)$$

问题变成了求解$(n!{)}^2$的质因子和每个质因子的阶数

我们可以先求$(n!)$的质因子和每个质因子的阶数后将阶数乘2就可以的到$(n!{)}^2$的解

如何求$(n!)$的质因子和质因子的阶数可以参考我的另一篇博客

AcWing 197.阶乘分解 题解

求得$(n!)$的所有质因子后将质因子的阶数乘2，最后利用因子个数的计算公式就可以得到k的所有取值

对于每一个k值都有一个x值与其对应，则最后的所有取值即为正整数数对的个数

完整代码

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)//线性筛
    {
    
        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++)//分解质因子
        {
    
            int tmp=n;
            int p=Primes[i];
            long res=0;
            while(tmp>0)
            {
    
                res+=tmp/p;
                tmp/=p;
            }
            res*=2;//转换成平方的质因子阶数
            ans=(ans%MOD)*((res+1)%MOD);//因子计算公式
            ans%=MOD;
        }
        System.out.println(ans);
    }
}