算法分析

做了这题，感觉这类题目的大多数分析过程都是这样的

• 求有多少对整数对(x,y)满足一条方程，则方程一定存在解，将y转换为关于x的表示式，再根据y的约数条件，求出(x,y)的匹配数，即一个x对应一个y

1、推表达式

$\frac{1}{x} + \frac{1}{y} = \frac{1}{n}$ 转换为y的表达式，求得
$y = \frac{x * n!}{x - n!} = \frac{(x - n! + n!) * n!}{x - n!} = \frac{(x - n!) * n!}{x - n!} + \frac{n!^2}{x - n!} = n! + \frac{n!^2}{x - n!}$

y的约数条件是y是正整数，因此$\frac{n!^2}{x - n!}$一定是一个整数，因此x > n!恒成立，
转化为问有多少个x使得$\frac{n!^2}{x - n!}$是一个整数，即等价于求$n!^2$一共有多少个约数

2、求$n!^2$一共有多少个约数，参考 Acwing197. 阶乘分解 的方法

假设$n!^2 = p_{1}^{2c_{1}} * p_{2}^{2c_{2}} * … *p_{k}^{2c_{k}}$，则约数的个数是$(2c_{1} + 1) * (2c_{2} + 1) * … * (2c_{k} + 1)$

时间复杂度 $O(n)$

参考文献

算法提高课

Java 代码

import java.util.Scanner;

public class Main {
    static int N = 1000010;
    static int mod = 1000000000 + 7;
    static int[] primes = new int[N];
    static int cnt = 0;
    static boolean[] st = new boolean[N];
    static void init(int n)
    {
        for(int i = 2;i <= n;i ++)
        {
            if(!st[i]) primes[cnt ++] = i;
            for(int j = 0;primes[j] * i <= n;j ++)
            {
                st[primes[j] * i] = true;
                if(i % primes[j] == 0) break;
            }
        }
    }
    public static void main(String[] args){
        Scanner scan = new Scanner(System.in);
        int n = scan.nextInt();
        init(n);
        long res = 1;
        for(int i = 0;i < cnt;i ++)
        {
            int p = primes[i];
            int s = 0;
            for(int j = n;j != 0;j /= p)
            {
                s += j / p;
            }
            res = (res * (2 * s + 1)) % mod;
        }
        System.out.println(res);
    }
}