题目描述
给你一个正整数 M M M 请你求出一个最小的正整数 N N N 满足 N 的阶层是 M 的倍速 N的阶层是M的倍速 N的阶层是M的倍速
由于M实在是太大了，为了方便你读入，善良的出题人给你K个整数e1，e2，e3…ek
e i ei ei的 i i i代表着第 i i i个素数，ei代表着ei个第i个素数相乘
比如e1为3，第1个素数是2，那么e1为M的贡献就是乘上 2 ∗ 2 ∗ 2 2*2*2 2∗2∗2
先考虑一个数怎么样才能整除另一个数（是另一个数的倍数）
一个数x拆分成若干个素数相乘，如果每个素数的数量都比另一个数y多，那么x就是y的倍数
这里给你的M就是写成若干个素数相乘的形式
然后很显然这个题有单调性，因为是连乘，如果N！能够整除M，那么（N+1）！也能
既然答案满足单调性，那我们就二分答案
那么check函数怎么写呢，对于一个数x!拆分之后含有多少个y，很显然有
x
/
y
+
x
/
（
y
∗
y
）
+
x
/
（
y
∗
y
∗
y
）
.
.
.
.
.
.
.
x/y+x/（y*y）+x/（y*y*y）.......
x/y+x/（y∗y）+x/（y∗y∗y）.......
为了防止爆 l o n g long long l o n g long long我们除就可以了
#include <bits/stdc++.h>
using namespace std;
const int N = 3e5 + 5;
//#define int long long
const int INF = 4e18+5;
#define F(i,l,r) for(int i=l;i<=r;i++)
#define R(i,l,r) for(int i=r;i>=l;i--)
#define vv vector
#define fi first
#define se second
#define pii pair<int,int>
typedef long long ll;
const int mod = 998244353;
//const int mod = 1e9+7;
const int M = 1e7+5;
int b[N],dp[50][N],vis[N],pri[N];
ll a[N];
int dx[4]={1,0,-1,0};
int dy[4]={0,1,0,-1};
int n,m,k,ans,x,y,n0,n2,m0,m2,op;
//map<int,int>mp;
map<int,int>mmap;
char mp[1005][1005];
vector<int>v[10];
int lowbit(int x) {
return x&-x;
}
char xx[N];
bool temp;
int kuai(int x,int y){
int sum=1;
x%=mod;
while(y){
if(y%2){
y--;
sum*=x;
sum%=mod;
}
x*=x;
y/=2;
x%=mod;
}
return sum;
}
void init(){
op=0;
F(i,2,10000){
if(!vis[i]){
pri[++op]=i;
vis[i]=1;
}
for(int j=1;i*pri[j]<=10000;j++){
vis[i*pri[j]]=1;
if(i%pri[j]==0) break;
}
}
}
struct node{
int sum,l,r,add;
}tree[N];
bool check(int x){
F(i,1,n){
int sum=0;
y=pri[i];
while(y<=x){
sum+=x/y;
y*=pri[i];
}
if(sum<a[i]) return false;
}
return true;
}
void solve()
{
cin>>n;
F(i,1,n) cin>>a[i];
int l=0,r=1e9+8;
while(l<r){
int mid=l+r>>1;
if(check(mid)) r=mid;
else l=mid+1;
}
cout<<r<<endl;
}
signed main()
{
ios::sync_with_stdio(false);
cin.tie(0), cout.tie(0); // cin.tie(nullptr);
int T = 1;
cin >> T;
init();
for (int i = 1; i <= T; i++)
{
solve();
}
return 0;
}