求2^a-13^b-1=c!的所有正整数解
首先,观察题目中的式子,可以发现其中的因子都是指数为质数的形式,因此我们可以考虑对式子进行质因数分解。
由于 $2$ 和 $3$ 都是质数,因此我们可以将 $(2^a-1)$ 和 $(3^b-1)$ 分别分解为:
$$2^a-1=(2-1)(2^{a-1}+2^{a-2}+...+2+1)$$
$$3^b-1=(3-1)(3^{b-1}+3^{b-2}+...+3+1)$$
因此,原式可以写为:
$$(2-1)(2^{a-1}+2^{a-2}+...+2+1)(3-1)(3^{b-1}+3^{b-2}+...+3+1)=c!$$
化简后得到:
$$(2^{a-1}+2^{a-2}+...+2+1)(3^{b-1}+3^{b-2}+...+3+1)=\frac{c!}{2\cdot3}$$
注意到 $2^{a-1}+2^{a-2}+...+2+1=2^a-1$,因此上式可以进一步化简为:
$$(2^a-1)(3^b-1)=\frac{c!}{2\cdot3}$$
由于 $c!$ 是一个正整数,因此 $\frac{c!}{2\cdot3}$ 也必须是一个正整数,即 $2\cdot3$ 必须是 $c!$ 的因子。
因此,我们可以枚举 $c$,对于每个 $c$,求出 $\frac{c!}{2\cdot3}$,然后判断是否存在整数 $a$ 和 $b$,使得 $(2^a-1)(3^b-1)=\frac{c!}{2\cdot3}$。
对于判断是否存在 $a$ 和 $b$ 的问题,我们可以使用类似于求解 $a^2+b^2=c$ 的方法,即从小到大枚举 $a$ 和 $b$,当 $(2^a-1)(3^b-1)$ 大于 $\frac{c!}{2\cdot3}$ 时,停止枚举 $b$,进行下一个 $a$ 的枚举。
这样做的时间复杂度为 $O(c\log c)$,可以通过本题。

原文地址: http://www.cveoy.top/t/topic/roh 著作权归作者所有。请勿转载和采集!