算法分析
做了这题,感觉这类题目的大多数分析过程都是这样的
- 求有多少对整数对
(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);
}
}
最开始的大多数题目分析总结挺好的
🐂逼
y的约数条件是y是正整数 –> 约数 –> 约束(hh强迫症
hh