2024 年北京预赛

思路

阶乘中质数p的指数等于 ${\sum }_{j\ge 1}\lfloor n/p^j\rfloor$，因为p的每一重因子分别由其倍数贡献；约分后分母指数取分母减分子的正部。

想法从哪来：只看某几个n的分母，无法排除以后出现更大的质数。应先固定一个质数p，问它在三个阶乘中会被抵消多少次。把指数写成取整和之后，对每个p的幂都只需研究n除以它的余数；当该幂大于常数项的两倍时，分母刚多出一次的区间已被分子覆盖，取整差不会为正。由此得到与n无关的上界。随后倒过来构造：让最大的候选质数刚好出现在移位后的阶乘，却还未进入另外两个阶乘。候选本身的素性以及上界附近没有更大质数，也要逐项检查，不能只凭“大数看起来像质数”。

先对每个素数比较三个阶乘中的指数，找出分母质因数的统一上界；再核候选数确为素数，并选一个下标使它刚进入分母而尚未进入分子。