阶乘时间限制1 秒空间限制256M网页链接牛客tracker牛客tracker 每日一题完成每日打卡即可获得牛币。获得相应数量的牛币能在【牛币兑换中心】换取相应奖品助力每日有题做丰盈牛币日益多题目描述给定一个正整数p pp。求一个最小的正整数n nn使得n ! n!n!是p pp的倍数。输入描述第一行输入一个正整数T TT表示测试数据组数。接下来T TT行每行一个正整数p pp。输出描述输出T TT行对于每组测试数据输出满足条件的最小的n nn。示例 1输入4 1 2 4 8输出1 2 4 4备注T ≤ 10 3 , p ≤ 10 9 T \le 10^3,\quad p \le 10^9T≤103,p≤109数据范围与提示1 ≤ T ≤ 10 3 1 \le T \le 10^31≤T≤1031 ≤ p ≤ 10 9 1 \le p \le 10^91≤p≤109核心思路对p pp做质因数分解p ∏ q i e i p \prod q_i^{e_i}p∏qiei​​。n ! n!n!能整除p pp即p ∣ n ! p \mid n!p∣n!等价于对每个质因子q i q_iqi​n ! n!n!中q i q_iqi​的指数不少于e i e_iei​。由勒让德公式Legendre’s formulan ! n!n!中质数q qq的指数为v q ( n ! ) ⌊ n q ⌋ ⌊ n q 2 ⌋ ⌊ n q 3 ⌋ ⋯ v_q(n!) \left\lfloor \frac{n}{q} \right\rfloor \left\lfloor \frac{n}{q^2} \right\rfloor \left\lfloor \frac{n}{q^3} \right\rfloor \cdotsvq​(n!)⌊qn​⌋⌊q2n​⌋⌊q3n​⌋⋯由于v q ( n ! ) v_q(n!)vq​(n!)关于n nn单调不减可对n nn在[ 1 , p ] [1, p][1,p]上二分答案对每个质因子检查指数是否达标。特殊处理p 1 p 1p1此时n 1 n 1n11 ! 1 1! 11!1是1 11的倍数。时间复杂度约为O ( T ( p log ⁡ p ⋅ π ( p ) ) ) O(T(\sqrt{p} \log p \cdot \pi(\sqrt p)))O(T(p​logp⋅π(p​)))在T ≤ 10 3 T \le 10^3T≤103、p ≤ 10 9 p \le 10^9p≤109范围内可轻松通过。注意用long long累加避免中间量溢出。解题思路本题是**质因数分解 勒让德公式阶乘中质因子指数**的经典问题。给定正整数p pp要求最小的n nn使得n ! n!n!是p pp的倍数即p ∣ n ! p \mid n!p∣n!。这等价于对p pp的每个质因子q qqn ! n!n!中q qq的指数不少于p pp中q qq的指数。因此可以先分解p pp再对每个质因子求出满足条件的最小n nn最后取最大值。1. 问题等价转化对p pp进行质因数分解p ∏ q i e i p \prod q_i^{e_i}p∏qiei​​。对于每个质因子q qq和指数e ee需要找到最小的n nn使得v q ( n ! ) ≥ e v_q(n!) \ge evq​(n!)≥e其中v q ( n ! ) v_q(n!)vq​(n!)是n ! n!n!中q qq的指数。由于v q ( n ! ) v_q(n!)vq​(n!)关于n nn单调递增可以从小到大逐个检查q qq的倍数累加其中q qq的指数直到总和达到e ee。所有质因子对应的最小n nn取最大值即为答案。若p pp本身含有大于p \sqrt{p}p​的质因子指数必为1 11则该质因子对应的最小n nn就是该质数本身。2. 算法实现读入测试组数T TT。对于每组数据读入p pp初始化答案ans 1令t p。从b 2 b 2b2开始枚举到t \sqrt{t}t​若t % b 0统计b bb的指数e并不断t / b。计算满足v b ( n ! ) ≥ e v_b(n!) \ge evb​(n!)≥e的最小n nn初始化x 0c 0。当c e时令x (x / b 1) * b即下一个b bb的倍数。计算当前x中b bb的因子个数累加到c。循环结束时x即为满足该质因子的最小n nn。更新ans max(ans, x)。循环结束后若t 1说明剩余一个质数其指数为1 11对应最小n nn为t更新ans max(ans, t)。输出ans。3. 复杂度分析质因数分解枚举到p \sqrt{p}p​复杂度O ( p ) O(\sqrt{p})O(p​)。对每个质因子计算最小n nn指数e ≤ log ⁡ 2 p ≈ 30 e \le \log_2 p \approx 30e≤log2​p≈30每次跳至下一个b bb的倍数循环次数不超过e ee因此非常快。总时间复杂度O ( T ⋅ p ) O(T \cdot \sqrt{p})O(T⋅p​)。T ≤ 10 3 T \le 10^3T≤103p ≤ 10 9 p \le 10^9p≤109p ≈ 3.2 × 10 4 \sqrt{p} \approx 3.2 \times 10^4p​≈3.2×104总运算量约3 × 10 7 3 \times 10^73×107完全可行。空间复杂度O ( 1 ) O(1)O(1)仅使用少量变量。总结通过将p pp分解质因数把问题转化为对每个质因子求最小的n nn使得n ! n!n!中该质因子的指数达标。利用逐个累加质因子指数的方法避免了二分查找实现简单且高效。最终取所有质因子对应n nn的最大值即为答案。代码简要说明主函数读入T TT循环调用S()。S()函数读入p pp初始化ans 1t p。枚举因子b从 2 到t \sqrt{t}t​若整除则统计指数e并缩小t。内部循环计算满足v_b(n!) e的最小nx从 0 开始每次跳到下一个b的倍数累加其中b的指数直到累加值c e。更新ans。若剩余t 1更新ans max(ans, t)。输出ans。代码内容#includebits/stdc.husingnamespacestd;#defineendl\ntypedeflonglongll;typedefunsignedlonglongull;typedefvectorvectorllvvt;typedefpairll,llpll;constll N1e310;constll INF1e18;constll M1e610;constll mod1e97;voidS(){ll p;cinp;ll r1;ll tp;for(ll b2;b*bt;b){if(t%b0){ll e0;while(t%b0){e;t/b;}ll x0;ll c0;while(ce){x(x/b1)*b;ll vx;while(v%b0){c;v/b;}}rmax(r,x);}}if(t1)rmax(r,t);coutrendl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cinT;while(T--)S();return0;}