阶乘
时间限制：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≤103
- 1 ≤ 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 formula），n ! 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 = 1p=1，此时n = 1 n = 1n=1（1 ! = 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 qq，n ! 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 = 2b=2开始枚举到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 = 0，c = 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≤log2p≈30，每次跳至下一个b bb的倍数，循环次数不超过e ee，因此非常快。
- 总时间复杂度：O ( T ⋅ p ) O(T \cdot \sqrt{p})O(T⋅p)。T ≤ 10 3 T \le 10^3T≤103，p ≤ 10 9 p \le 10^9p≤109，p ≈ 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 = 1，t = p。 - 枚举因子
b从 2 到t \sqrt{t}t，若整除则统计指数e，并缩小t。 - 内部循环计算满足
v_b(n!) >= e的最小n：x从 0 开始，每次跳到下一个b的倍数，累加其中b的指数，直到累加值c >= e。 - 更新
ans。 - 若剩余
t > 1，更新ans = max(ans, t)。 - 输出
ans。
- 读入p pp，初始化
代码内容
#include<bits/stdc++.h>usingnamespacestd;#defineendl'\n'typedeflonglongll;typedefunsignedlonglongull;typedefvector<vector<ll>>vvt;typedefpair<ll,ll>pll;constll N=1e3+10;constll INF=1e18;constll M=1e6+10;constll mod=1e9+7;voidS(){ll p;cin>>p;ll r=1;ll t=p;for(ll b=2;b*b<=t;b++){if(t%b==0){ll e=0;while(t%b==0){e++;t/=b;}ll x=0;ll c=0;while(c<e){x=(x/b+1)*b;ll v=x;while(v%b==0){c++;v/=b;}}r=max(r,x);}}if(t>1)r=max(r,t);cout<<r<<endl;}intmain(){ios::sync_with_stdio(0);cin.tie(0),cout.tie(0);intT;cin>>T;while(T--)S();return0;}
