题意简述
我们根据唯一分解定理得到，对于每一个数 \(x\) 可以表示成 \(\sum p_i^{e_i}\) 的形式，其中 \(p_i\) 表示第 \(i\) 大的素数。
我们重新定义两个数之间的比较，对于两个数 \(x,y\) ：
-
如果 \(x=y\) ，两个数相等
-
如果 \(x,y\) 不相等，我们就从小到大枚举素数，知道找到一个下标 \(j\) 满足对于 \(i<j\) 两个数的 \(e_i\) 相等，但是 \(e_j\) 不相等。\(e_j\) 大的更大。比如 \(2>7\) 。
我们现在有两个序列，长度分别为 \(n,m\) 。我们将两个序列的 \((i,j)\) 变成 \(a_i\times b_j\) 放入一个新的序列 \(c\) 。问我们将 \(c\) 从小到大排序后，第 \(k\) 个数是多少。 \(n,m \leqslant 1e5,k \leqslant nm\) 。
思路点拨
我们考虑到一个性质: \(a \leqslant x\) 并且 \(b \leqslant y\) ，就会有 \(ab \leqslant xy\) 。这个结论显然但是重要。
因为 \(k\) 个数我们枚举是不可行的，所以我们考虑二分这个答案。对于 \(a_i \times b_j\) ,我们该如何计数？我们可以在序列 \(a\) 中枚举一个 \(id_i\) ,在序列 \(b\) 中找到 \(id_j\) 使得 \(a_{id_i}\times a_{id_j}\) 是尽量接近 \(a_i\times b_j\) 的。由于我们刚刚的性质，可以知道，在 \(id_i\) 不断变大的过程中， \(id_j\) 会渐渐变小。我们双指针可以求出这个答案。
但是实际上，在二分的过程中我们需要选择一个节点 \(mid\) 来比较，但是这题中这个点并不好找。我们考虑一个区间 \([l,r]\) ，注意，这个区间并不是一个连续的区间，因为题解中的大小是按照题目规定来的。那么我们可以找到有多少个 \((i,j)\) 有 \(l < a_i \times a_j <r\) ，在这些点中随机一个值，这样的期望时间和二分是一样的。但是这个值怎么找呢？
还是利用单调性。这一点可以留给读者自己思考。
代码
原题对常数的要求比较严格，我的这份代码并不可以通过，仅供参考：
#include<bits/stdc++.h>
#define int long long
using namespace std;
inline int read(){
int x=0,f=1;
char ch=getchar();
while(ch<'0'||ch>'9'){
if(ch=='-') f=-f;
ch=getchar();
}
while(ch>='0'&&ch<='9'){
x=x*10+ch-'0';
ch=getchar();
}
return x*f;
}
const int MAXN=5e5+10;
int n,m,k;
struct node{
vector<int> p;//质因子
void clear(){p.clear();}
bool friend operator<(const node &A,const node &B){
int len=min(A.p.size(),B.p.size());
for(int i=0;i<len;i++){
if(A.p[i]==B.p[i]) continue;
else return A.p[i]>B.p[i];
}
return A.p.size()<B.p.size();
}
bool friend operator==(const node &A,const node &B){
if(A.p.size()!=B.p.size())
return 0;
int len=A.p.size();
for(int i=0;i<len;i++){
if(A.p[i]==B.p[i]) continue;
return 0;
}
return 1;
}
bool friend operator>=(const node &A,const node &B){
if(A<B) return 0;
return 1;
}
}temp;
node merge(node x,node y){
temp.p.clear();
for(int i=0,j=0;(i<x.p.size())||(j<y.p.size());)
if ((i!=x.p.size())&&((j==y.p.size())||(x.p[i]<y.p[j])))temp.p.push_back(x.p[i++]);
else temp.p.push_back(y.p[j++]);
return temp;
}
const int N=1e6;
int vis[N+10];
vector<int> o[N];
void init(){
for(int i=2;i<=N;i++){
if(vis[i]) continue;
o[i].push_back(i);
for(int j=i*2;j<=N;j+=i){
vis[j]=1;
o[j].push_back(i);
}
}
}
node a[MAXN],b[MAXN];
node split(int x){
temp.clear();
int y=x;
for(int i=0;i<o[x].size();i++){
while(y%o[x][i]==0){
temp.p.push_back(o[x][i]);
y/=o[x][i];
}
}
return temp;
}
int ft[MAXN],ed[MAXN];
int run(node k){
int ans=0;
for(int i=1,j=m;i<=n;i++){
while (j&&(k<merge(a[i],b[j]))) j--;
int s_i=i,s_j=j;
while (j&&(k==merge(a[s_i],b[j]))) j--;
while (i&&(k==merge(a[i],b[s_j]))) i++;
ans+=(i-s_i)*(s_j-j);
}
return ans;
}
int fun(node A){
int ans=0;
for(int l=1,r=m;l<=n;l++){
while(r&&A<merge(a[l],b[r]))
r--;
ans+=r;
}
return ans;
}
int solve(){
node L=merge(a[1],b[1]),R=merge(a[n],b[m]);
while(1+1==2){
ft[0]=ed[0]=m;
int useful=0;//在二分的值域内存在的有用点对
for(int i=1;i<=n;i++){
ft[i]=ft[i-1],ed[i]=ed[i-1];
while(ft[i]>1&&!(merge(a[i],b[ft[i]-1])<L)) ft[i]--;
while(ed[i]&&R<merge(a[i],b[ed[i]])) ed[i]--;
useful+=(ed[i]-ft[i]+1);
}
if(useful==run(L)+run(R)) break;//此时[l,r]之间没有除了l,r之外的决策点
int kk=rand()%useful+1,l,r;
for(int i=1;i<=n;i++){
if(ed[i]-ft[i]+1<kk)
kk-=(ed[i]-ft[i]+1);
else{
l=i;
r=ft[i]+kk-1;
break;
}
}
node mid=merge(a[l],b[r]);
if(fun(mid)<=k) L=mid;
else R=mid;
}
int cnt=1;
for(int i=0;i<L.p.size();i++) cnt*=L.p[i];
return cnt;
}
signed main(){
srand(time(0));
int T=read();
init();//筛法
while(T--){
n=read(),m=read(),k=read();
for(int i=1;i<=n;i++){
int x=read();
a[i]=split(x);
}
for(int i=1;i<=m;i++){
int x=read();
b[i]=split(x);
}
sort(a+1,a+n+1);
sort(b+1,b+m+1);
cout<<solve()<<endl;
}
return 0;
}