自动搬运

查看原文

来自洛谷，原作者为

	Hog_Dawa_IOI 铃兰已凋谢，水獭犹可追

搬运于2025-08-24 22:59:41，当前版本为作者最后更新于2025-07-09 09:24:13，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

只是校内模拟赛出了这个题而已。

我们刚看到这个 $n,k < 2^{63}$，会觉得很头大。
我们尝试把 $k$ 写成 $p_1^{a_1} \times p_2^{a_2} \times p_3^{a_3} \times \dots \times p_N^{a_N} $ 的形式，这样的话 $f_k=\dfrac{(\sum_{i=1}^{N} a_i)!}{\prod_{i=1}^{N} (a_i !)}$。这是一个组合数问题，先把所有质因数排列，再除掉每一种相同的组合数内部打乱排列的方案。
于是我们发现这和 $p$ 完全没有关系。
又因为我们想要让 $k$ 尽量小，所以 $p$ 要尽量小，尽量取到 $2,3,5,7,\dots$，按从小到大的顺序是最优的。
经过计算，$2 \times 3 \times 5 \times 7 \times 11 \times 13 \times 17 \times 19 \times 23 \times 29 \times 31 \times 37 \times 41 \times 43 \times 47 \times 53 > 2^{63}-1$，因此实际上我们只需要这么多个质数（一共有 $16$ 个）。
而且我们发现这和 $a_i$ 的顺序也没有关系。这意味着在 $a_i$ 们相同的情况下，越大的 $a_i$ 应该配对越小的 $p_i$。因此可以得到 $a_1 \ge a_2 \ge a_3 \ge \dots \ge a_N$。
当 $a_1=63$ 时，$k=2^{63}$，刚好超出范围，因此 $a_1 \le 63$。

于是我们得到了两个非常重要的性质。
$16$ 个质数是非常可以爆搜的，而且 $a$ 的范围也小的可怜。而且随着 $p_i$ 的增大，$a_i$ 的取值范围也越来越小，状态数也越来越少。因此我们爆搜每种 $a$ 的取值情况，同时用 map 记录答案，最后询问时在 map 中查找答案。
那么问题来了，如何时刻算出当前 $a$ 的取值下 $f_k$ 的值？
我们设当前走到第 $x$ 位，$\sum_{i=1}^{x-1} a_i=A,\prod_{i=1}^{x-1} (a_i !)=B$，那么 $f_k=\dfrac{(A +a_x)!}{B\times(a_x!)}$。
现在我们把 $a_x$ 增加 $1$，那么 $f_k=\dfrac{(A +a_x+1)!}{B\times((a_x+1))!)}=\dfrac{(A +a_x)!\times (A+a_x+1)}{B\times(a_x!)\times(a_x+1)}$。
观察得到，新的值只比原值多了 $\dfrac{A +a_x+1}{a_x+1}$ 这么一坨，而它是已知的。所以随着 $a_x$ 的增加，$f_k$ 的值是可以顺便求出的。
那么就可以很方便的在 map 中记录值了。
网上也看到预处理出阶乘的值最后再计算，也不是不行。

需要注意，如果你当前的方案数或数字 $\ge 2^{63}$，那么这就是无效状态，可以不往下走了。
不过为了保险，我还是开了 __int128。绝对不是因为我过不去。
快的飞起，战绩可查。

#include<map>
#include<cstdio>
using namespace std;
const __int128 mx=9223372036854775807;
long long n;int zhi[20],cntt[20];
map<long long,long long>as;
void dfs(int wh,int cnt,__int128 cc,__int128 num)
{
	if(num>mx) return;if(wh>16) return;
	if(cnt)
	{
		long long x=(long long)cc,y=(long long)num;
		if(!as[x]) as[x]=y;
		else if(as[x]>y) as[x]=y;
	}
	__int128 dq=1;for(cntt[wh]=0;
	num*dq<=mx&&cntt[wh]<cntt[wh-1];)
	dq*=zhi[wh],cntt[wh]++,cc=cc*
	(cnt+cntt[wh])/(cntt[wh]),
	dfs(wh+1,cnt+cntt[wh],cc,num*dq);
}
int main()
{
	zhi[1]=2,zhi[2]=3,zhi[3]=5,zhi[4]=7,
	zhi[5]=11,zhi[6]=13,zhi[7]=17,zhi[8]=19,
	zhi[9]=23,zhi[10]=29,zhi[11]=31,zhi[12]=37,
	zhi[13]=41,zhi[14]=43,zhi[15]=47,zhi[16]=53;
	cntt[0]=63,dfs(1,0,1,1);
	while(scanf("%lld",&n)!=EOF)
	printf("%lld %lld\n",n,as[n]);
}