题目大意
给定一个数 \(n\)，求两个数 \(a\)，\(b\)，使 \(\Large\frac{a!}{b!}\normalsize = n(a>b)\)。
若有无数组解输出-1。
多组数据。
思路简析
\[a! = a\times(a-1)\times(a-2)\times\cdots\times2\times1 \]\[b! = b\times(b-1)\times(b-2)\times\cdots\times2\times1 \]所以
\[\frac{a!}{b!} = a\times(a-1)\times(a-2)\times\cdots\times(b+1)\times b = \prod_{i=b}^{a} i \]即求一段连续数列的积。
简单思考下：因为乘法增长速率是很快的，所以只需要观察每个 \(n\)。
呃呃我也不知道怎么说，但是你想：
\(\sqrt[1]{n} = n\)
\(\sqrt[2]{n} \times \sqrt[2]{n} = n\)
\(\sqrt[3]{n} \times \sqrt[3]{n} \times \sqrt[3]{n} = n\)
\(\sqrt[4]{n} \times \sqrt[4]{n} \times \sqrt[4]{n} \times \sqrt[4]{n} = n\)
\(\sqrt[5]{n} \times \sqrt[5]{n} \times \sqrt[5]{n} \times \sqrt[5]{n} \times \sqrt[5]{n} = n\)
\(\cdots\)
\(1 < \sqrt[n]{n} < 2\)
由于 \(a\)、\(b\) 都是正整数，所以显然不是小数。
然后就能遍历长度（\(a-b\)）来进行判断。
E.G.:
\(5! = 120\)
\(\sqrt[5]{120} = 120^{\frac{1}{5}} \approx 3\)
而 \(4 \cdot 5 \cdot 6 = 120\).
显然能得到一个结论即在 \(\sqrt[x]{n}\) 附近的 \(x\) 个数才有可能符合条件。
那么求出 \(\sqrt[x]{n}\) 再用其求即可。
点击查看代码
/*
compiling in hszxoj
standard C++14 -O2
ide VScode
g++ test.cpp -o test && ./test
*/
#include <bits/stdc++.h>
// #include <bits/extc++.h>
namespace {
#define filein(x) freopen(x".in", "r", stdin)
#define fileout(x) freopen(x".out", "w", stdout)
#define file(x) filein(x), fileout(x)
using namespace std;
// using namespace __gnu_pbds;
#define ll long long
#define db double
#define un unsigned
#define ui un int
#define ull un ll
#define udb un db
template <typename T>
using pr = pair<T, T>;
#define pii pr<int>
#define pll pr<ll>
#define pdb pr<db>
#define fir first
#define sec second
#define mp(x, y) make_pair(x, y)
const int man = 2.5e5+10, mam = 2.5e5+10;
}
int T;
ll n;
priority_queue<pii, vector<pii >, greater<pii > > q;
void pres () ;
int main () {
pres();
scanf("%d", &T);
while (T --) {
scanf("%lld", &n);
if (n == 1) puts("-1");
else {
int res = 0, l, r;
ll np;
for (int i = 2; i <= n; ++ i) {
db p = pow(n, 1.0/db(i));
if (p < 2) break; // * = i√n
np = 1, l = max(1, int(p-i)), r;
for (r = max(int(p-i+1), 1); r <= p; ++ r) np *= r;
-- r;
for (int j = p-i+1; j <= min((ll)(p+i-1), n); ++ j) {
// if (i == 2) printf("AAK%d %d %lld %d %d\n", i, int(p), np, l, r);
if (np==n && r-l == i) {
++ res;
q.push(mp(r, l));
break;
} if (r-l == i) np /= ++l;
// if (i == 2) printf("BBK%d %d %lld %d %d\n", i, int(p), np, l, r);
np *= ++r;
}
} printf("%d\n", res+1);
while (q.size()) {
printf("%d %d\n", q.top().fir, q.top().sec);
q.pop();
} printf("%lld %lld\n", n, n-1);
}
} return 0;
}
// ---
void pres () {
// #ifndef ONLINE_JUDGE
file("jc");
// #endif
return ;
}