Link.
Description.
给定一个长度为 \(n\) 的序列，是一个 \([l,\dots,r]\) 的排列。
给定 \(n\)，每次可以询问任意不同两个的 \(\text{lcm}\)，要在 \(n+5000\) 的复杂度内问出序列。
Solution.
小数据暴力
首先有个很显然的询问数 \(\frac {n\cdot(n-1)}2\) 的做法。
解一下方程发现 \(\frac{n\cdot (n-1)}2=n+5000\) 的解大概是 101.511249367。
所以有一个显然的 \(O(n^3)\) 做法，找到最大的数，它必定是 \((r-1)\cdot r\)。
然后每次找到没标记过的 \(i\cdot (i-1)\) 即可。
大数据随机
我们发现在长度比较长的情况下，质数分布概率是比较高的，大概是 \(\frac 1{\log n}\ge\frac 1{20}\)。
考虑随机 rand \(10000\) 个数，其中没有质数的概率是 \(1-\left(\frac {19}{20}\right)^{10000}\)，已经很小了。
然后我们找到了质数的情况下，可以直接去问它和任意数的 \(\text{lcm}\) 然后就可以 \(n-1\) 次询问得到整个序列。
Attention.
- 他妈多组询问的交互题就是屑，一个点 WA 会导致后面的 tests TLE，然后让我以为我质因数分解太慢了，调了一年。
- 这题很牛逼，如果小数据暴力没开到 100，就也会挂，大概就有一段长度为 \(85\) 的区间 \([155922,156006]\) 里面没有一个质数，所以小数据暴力一定要开尽量大。
- 因为这题很显然我们需要分解的数虽然很大，但是它 \(2,3\) 等较小数出现概率比较高，所以直接暴力分解是可以的。
Coding.
点击查看破烂代码
//是啊，你就是那只鬼了，所以被你碰到以后，就轮到我变成鬼了{{{
#include<bits/stdc++.h>
using namespace std;typedef long long ll;
template<typename T>inline void read(T &x)
{
x=0;char c=getchar(),f=0;
for(;c<48||c>57;c=getchar()) if(!(c^45)) f=1;
for(;c>=48&&c<=57;c=getchar()) x=(x<<1)+(x<<3)+(c^48);
f?x=-x:x;
}
template<typename T,typename...L>inline void read(T &x,L&...l) {read(x),read(l...);}/*}}}*/
const int N=1000005;int n,a[N],id[N],rs[N],vs[N];ll vl[105][105];
int pr[N],pc,ls[N],ph[N],mu[N];char pv[N];//prinit{{{
inline void prinit(int n)
{
pv[1]=mu[1]=ph[1]=1,ls[1]=0;for(int i=1;i<=n;i++)
{
if(!pv[i]) pr[++pc]=i,mu[i]=-1,ph[i]=i-1,ls[i]=i;
for(int j=1;j<=pc&&i*pr[j]<=n;j++)
{
ls[i*pr[j]]=pr[j],mu[i*pr[j]]=i%pr[j]?-mu[i]:0;
ph[i*pr[j]]=ph[i]*(pr[j]-!!(i%pr[j]));
pv[i*pr[j]]=1;if(i%pr[j]==0) break;
}
}
}//}}}//
#ifdef ONLINE_JUDGE
inline ll qry(int x,int y) {printf("? %d %d\n",x,y),fflush(stdout);ll r;return read(r),r;}
#else
inline ll qry(int x,int y) {return 1ll*a[x]*a[y]/__gcd(a[x],a[y]);}
#endif
inline void baoli()
{
#ifndef ONLINE_JUDGE
for(int i=1;i<=n;i++) read(a[i]);
#endif
ll mx=0;for(int i=1;i<=n;i++) for(int j=i+1;j<=n;j++)
mx=max(mx,vl[i][j]=vl[j][i]=qry(i,j));
int r=sqrt(mx)-3,l;r=max(r,1),l=r-n+1;while(1ll*r*(r-1)!=mx) r++,l++;
for(int i=1;i<=n;i++) rs[i]=0;
for(int nw=r;nw>l;nw--)
{
int wa,wb;for(int i=1;i<n;i++) for(int j=i+1;j<=n;j++)
if(!rs[i]&&!rs[j]&&vl[i][j]==1ll*nw*(nw-1)) wa=i,wb=j;
int wh=wa;for(int i=1;i<=n;i++) if(wa^i&&vl[wa][i]%nw) {wh=wb;break;}
rs[wh]=nw;
}
for(int i=1;i<=n;i++) if(!rs[i]) rs[i]=l;
putchar('!');for(int i=1;i<=n;i++) printf(" %d",rs[i]);
putchar('\n'),fflush(stdout);
}
inline int fac(ll x)
{
int rs=0;for(int i=1;i<=pc&&x>1000000;i++) if(x%pr[i]==0)
{rs=max(rs,pr[i]);while(x%pr[i]==0) x/=pr[i];}
while(x^1) rs=max(rs,ls[x]),x/=ls[x];
return rs;
}
inline void real()
{
#ifndef ONLINE_JUDGE
for(int i=1;i<=n;i++) read(a[i]);
#endif
int mx=0,ma=0,mb=0;ll mw=0;for(int i=1;i<=5000;i++)
{
int a=rand()%n+1,b=rand()%n+1;if(a==b) b=b%n+1;
ll mv=qry(a,b);int vl=fac(mv);if(vl>mx) mx=vl,ma=a,mb=b,mw=mv;
}
int qwq=rand()%n+1;while(qwq==ma||qwq==mb) qwq=rand()%n+1;
if(qry(qwq,ma)%mx) swap(ma,mb);
//cerr<<"debug : "<<ma<<" "<<mx<<","<<mw/mx<<"=="<<a[ma]<<endl;
rs[ma]=mx,rs[mb]=mw/mx;for(int i=1;i<=n;i++) if(i!=ma&&i!=mb) rs[i]=qry(ma,i)/mx;
putchar('!');for(int i=1;i<=n;i++) printf(" %d",rs[i]);
putchar('\n'),fflush(stdout);
}
inline void solve() {read(n);if(n<=101.511249367) return baoli();else return real();}
int main() {int Ca;for(prinit(N-1),read(Ca),srand(time(0));Ca--;) solve();return 0;}