题意
有(T)组数据。
给定(p)，求最小的正整数(n)，使得(n!\%p=0)。
由于(p)很大，输入将给出(m)和(e_1,e_2...e_m)，表示(p=prod_{i=1}^mpr_i^{e_i})，其中(pr_i)是第(i)个质数。
数据范围:设(a_i=pr_i*e_i(i=1,2...m))
(T<=10^4,m<=100,a_i<=10^{18})
思路
注意到(m)很小，我们可以预处理出前100个质数。
一个暴力的做法是预处理出(n!)里面包含前100个质数的次方数，然后二分(n)，由于此题的答案上界为(a_i)，所以不可取。
一个观察是因为(p=prod_{i=1}^mpr_i^{e_i})，可以把(p)按照(pr_i^{e_i})拆分开考虑。
假设对于(p_i=pr_i^{e_i})，此时的答案为(ans_i)，那么对于(p=prod_{i=1}^mp_i)，
最后的答案一定是(max(ans_1,ans_2...ans_m))。这是显然的。
现在考虑如何求出(ans_i)。
等价于满足(n!)中包含(pr_i)的因子(>=e_i)的最小的n。
而(n!)中包含(pr_i)的因子数为(sum_{j=1}^{+infty}lfloorfrac{n}{{pr}_i^j} floor)。
于是我们可以二分(ans_i)，最后取(n=max(ans_1,ans_2...ans_m))即可。
时间复杂度为(O(Tmlog^2a_i))。
这样只能拿65分。
考虑一个优化，我们二分(ans_i)时，可以把下界调整到前面算出来的答案，即(max(ans_1,ans_2...ans_{i-1}))。而感觉上(ans_i)与(a_i)相差不是很大，于是我们可以先求出最大的那个(a_i)对应的(ans_i)，然后把之后的二分下界都改成这个(ans_i)，这样显然不会对答案造成影响，而之后的(a_i)都要比最大的(a_i)要小。
时间复杂度为(O(T(mloga_i+loga_i)))。
通过了全部数据并且都<=100ms。
代码
# include<bits/stdc++.h>
using namespace std;
# define lowbit(x) ((x)&(-x))
# define pi acos(-1.0)
# define eps 1e-8
# define MOD 1000000007
# define INF 1000000000
# define mem(a,b) memset(a,b,sizeof(a))
# define FOR(i,a,n) for(register int i=a; i<=n; ++i)
# define FDR(i,a,n) for(register int i=a; i>=n; --i)
# define bug puts("H");
# define lch p<<1,l,mid
# define rch p<<1|1,mid+1,r
# define mp make_pair
# define pb push_back
typedef pair<int,int> PII;
typedef vector<int> VI;
# pragma comment(linker, "/STACK:1024000000,1024000000")
typedef long long LL;
inline LL Scan() {
LL x=0;int f=1; char ch=getchar();
while(ch<'0'||ch>'9'){if(ch=='-') f=-1; ch=getchar();}
while(ch>='0'&&ch<='9'){x=x*10+ch-'0'; ch=getchar();}
return x*f;
}
const int N=50005;
//Code begin....
int T, m;
LL x;
int a[105];
LL b[105];
struct Node{LL b; int id;}node[105];
void init_p(){
a[0]=2;
int cnt=0, P=2;
while (1) {
++P;
bool flag=false;
FOR(i,0,cnt) if (P%a[i]==0) {flag=true; break;}
if (flag) continue;
a[++cnt]=P;
if (cnt>=99) break;
}
}
LL check(LL x, int id){
LL now=a[id], res=0;
while (now<=x) res+=x/now, x/=now;
return res;
}
LL sol(int id, LL x, LL tmp){
LL l=tmp/a[id], r=x, mid;
while (l<r) {
mid=(l+r)>>1;
if (check(mid*a[id],id)>=x) r=mid;
else l=mid+1;
}
return r*a[id];
}
bool comp(Node c, Node d){return c.b*a[c.id]>d.b*a[d.id];}
int main ()
{
init_p();
scanf("%d",&T);
while (T--) {
LL ans=1, ma=0;
scanf("%d",&m);
bool flag=true;
FOR(i,0,m-1) node[i].b=Scan(), node[i].id=i, ma=max(ma,node[i].b*a[i]);
sort(node,node+m,comp);
FOR(i,0,m-1) {
if (ma/100>node[i].b*a[node[i].id]) continue;
ans=max(ans,sol(node[i].id,node[i].b,ans));
if (node[i].b) flag=false;
}
if (flag) puts("1");
else printf("%lld
",ans);
}
return 0;
}