题解 CF1114E 【Arithmetic Progression】
AThousandSuns
·
·
题解
在我的博客上看效果更佳：点这里
看，第二个操作，明显暗示我们要二分最大值。（除了这个也没啥用了吧？）
用掉 \log 10^9=30 个操作。
令 mx 为我们二分出的最大值。
设公差为 d，那么 \forall 1\le i\le n,d|(mx-a_i)。
也就是如果我们知道的 a_i 有 x_1,x_2,x_3\dots,x_k，那么 d|\gcd(mx-x_1,mx-x_2,mx-x_3\dots,mx-x_k)。
但这样就有一个严峻的问题：如果 k 不够大，直接 \gcd 得到的可能不是答案！
无路可走了，只有一个想法：随机！
我们随机 30 个 i，询问这些 a_i 的值。（为什么要随机呢？因为如果直接取前 30 个 a_i 很可能会被毒瘤卡掉）
？？？这样不会错吗？
分析一下，我们设 $a_1=mx-k_1d,a_2=mx-k_2d\dots a_n=mx-k_nd$。那么我们求出的 $\gcd$ 就是随机出的 $30$ 个 $k_i$ 的 $\gcd$。
在 $10^6$ 中随机选 $30$ 个数，$\gcd$ 不为 $1$ 的概率就是出错的概率。
大致估算一下：
选出的 $k$ 都是 $2$ 的倍数的概率是 $\frac{1}{2^{30}}$。
选出的 $k$ 都是 $3$ 的倍数的概率是 $\frac{1}{3^{30}}$。
等等等等……
这样估算的话，出错概率是不会超过 $10^{-8}$ 的。
其实有更准确的求法，就是莫比乌斯反演，但由于我们只是来证明正确性的，就不讲了。
直接引用官方题解：
By some maths, we can find out the probability of our solution to fail being relatively small — approximately $1.86185\times 10^{-9}$.
直接上rand()就做完了……
了吗？
对了，这就是出题人恶毒所在了……
rand()和random_shuffle()的上界都是32767，访问不到后面大部分的元素。
于是出题人就把恶毒的数放在了前面……
那就用自己的rand()啊！写过treap吗？把那个rand搬过来就能用了！
**（注：这样在CF容易被卡掉，最近发现了一个叫做mt19937的东西，可以在[这里](http://codeforces.com/blog/entry/61587)看）**
```cpp
#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
typedef pair<int,int> PII;
const int maxn=1000100;
#define MP make_pair
#define PB push_back
#define lson o<<1,l,mid
#define rson o<<1|1,mid+1,r
#define FOR(i,a,b) for(int i=(a);i<=(b);i++)
#define ROF(i,a,b) for(int i=(a);i>=(b);i--)
#define MEM(x,v) memset(x,v,sizeof(x))
inline int read(){
char ch=getchar();int x=0,f=0;
while(ch<'0' || ch>'9') f|=ch=='-',ch=getchar();
while(ch>='0' && ch<='9') x=x*10+ch-'0',ch=getchar();
return f?-x:x;
}
int n,cnt,pt[maxn];
inline int rnd(){ //自己的rand
static int seed=2333;
return seed=(((seed*666666ll+20050818)%998244353)^1000000007)%1004535809;
}
int gcd(int x,int y){
return y?gcd(y,x%y):x;
}
int main(){
n=read();
if(n<=60){ //n<=60，随便玩
int mx=0,mn=INT_MAX;
FOR(i,1,n){
printf("? %d\n",i);
fflush(stdout);
int x=read();
mx=max(mx,x);
mn=min(mn,x);
}
printf("! %d %d\n",mn,(mx-mn)/(n-1));
fflush(stdout);
return 0;
}
int l=0,r=1e9;
while(l<r){ //二分最大值
int mid=(l+r)>>1;
printf("> %d\n",mid);
cnt++;
fflush(stdout);
int ver=read();
if(ver) l=mid+1;
else r=mid;
}
int mx=r,ans=0;
FOR(i,1,n) pt[i]=i;
FOR(i,1,n) swap(pt[i],pt[rnd()%n+1]);
FOR(i,1,min(n,60-cnt)){ //随机60-cnt个元素
printf("? %d\n",pt[i]);
fflush(stdout);
int x=read();
ans=gcd(ans,mx-x); //取gcd
}
printf("! %d %d\n",mx-(n-1)*ans,ans); //首项=末项-(项数-1)*公差
fflush(stdout);
}
```