自动搬运

查看原文

来自洛谷，原作者为

	vectorwyx 打 OI 就像心跳一样自然，退役就像去世一样必然。

搬运于2025-08-24 22:40:14，当前版本为作者最后更新于2022-10-13 20:24:43，作者可能在搬运后再次修改，您可在原文处查看最新版

自动搬运只会搬运当前题目点赞数最高的题解，您可前往洛谷题解查看更多

以下是正文

---

好题，yzy 神中神 orz。

先来考虑 Sub2，也就是已知 $p,k\bmod p,2b\bmod p$ 怎么做。为方便行文以下如无特殊说明提到 $k,b$ 均默认为模 $p$ 意义下。一个自然的思路是二分，每次询问 $g(1)+g(x)$，如果 $[1,x)$ 中没有拐点答案应为 $(x+1)k+2b$，否则为 $xk+2b$。在已知 $k,2b$ 且 $k\not= 0$ 时可以据此判断出拐点所在位置，询问次数为 $\log_2n=30$。

接下来考虑 Sub3，也就是赛时的正解。Sub3 在 $P$ 改为 $50$ 的同时多了 $12$ 次询问，由前文不难想到我们应当用多出来的这 $12$ 次询问确定一个合适的 $p$，满足 $k\bmod p\not= 0$，在确定 $p$ 的同时还需要确定 $k,2b$ 的取值。

先解决第一个问题，对于某个 $p$ 如何判断 $k$ 在模 $p$ 意义下是否为 $0$。首先一次询问就确定不现实，因为这里有 $k,b$ 两个变量。两次的话只需要任选三个数 $x<y<z$ 满足 $y+1<z$ 然后询问 $g(x)+g(y)$ 与 $g(x)+g(z)$，将询问结果作差得到 $a=g(z)-g(y)=(z-y)k$ 或 $(z-y-1)k$，由于 $y+1<z$，$a=0$ 当且仅当 $k=0$。即 $k\bmod p=0\iff g(x)+g(y)=g(x)+g(z)$。

第二个问题是在找到一个合法的 $p$ 后如何求出 $k,2b$。考虑能否利用检验 $k\bmod p\not= 0$ 时得到的 $g(x)+g(y)$ 与 $g(x)+g(z)$ 来解出 $k,2b$。这看上去是一个模意义下的二元一次方程，可惜由于拐点的存在，未知元 $k$ 的系数是不确定的。好在当 $x+1=y,z+1=x$ 时我们能够根据交互库是否返回 -1 来排除拐点的影响，即询问 $s=g(x-1)+g(x)$ 与 $t=g(x)+g(x+1)$，如果两者中有任意一个返回了 -1 可以直接确定拐点，否则两个方程是确定的：

$$\begin{cases} (2x-1)k+2b=s\\ (2x+1)k+2b=t\\ \end{cases}\iff \begin{cases} k=\dfrac{t-s}{2}\\ 2b=s-\dfrac{(2x-1)(t-s)}{2} \end{cases} $$

不妨令 $x=2$，则有：

$$\begin{cases} k=\dfrac{t-s}{2}\\ 2b=\dfrac{3s-t}{2} \end{cases} $$

这里需要用到 $2$ 的逆元，如果 $2|p$ 那么 $k,2b$ 就又不确定了，因此 $p$ 的取值只能为奇数。现在需要从 $[1,50]$ 中选 $12/2=6$ 个奇数出来，满足它们中至少有一个能整除斜率 $k$，显然这 $6$ 个数的 $\operatorname{lcm}$ 越大越容易成功，问题变为选出 $\operatorname{lcm}$ 最大的 $6$ 个奇数。可以写个 dfs 搜，也可以直接手动构造，思路是贪心，从大到小选，每次选一个对当前 $\operatorname{lcm}$ 贡献最大的数丢进集合里，这个贪心在范围大的时候不对，但是范围小的时候能凑合着用。按这个思路选出来的数是 $49,47,45,43,41,37$，其 $\operatorname{lcm}$ 为 $6760214685$，设为 $B$。那么它够不够用呢？由于题目只给了 $g(x)$ 的上界，所以我们还需要分析一下斜率 $k$ 的上界。令 $g(x)$ 的上界为 $A$，则：

$$\begin{gathered} 0\le k+b\le nk+b\le A\\ -b\le k\le \dfrac{A-b}{n} \end{gathered} $$

令 $b'=-b$，由 $-b\le \dfrac{A-b}{n}$ 得 $nb'\le A+b'\iff b'\le\dfrac{A}{n-1}$。那么 $k\le\dfrac{A+b'}{n}\le \dfrac{A+\frac{A}{n-1}}{n}=\dfrac{A}{n-1}$。对于 Sub5，将 $n=1162261531,A=7857125847061472735$ 代入得 $A\le6760204690<B=6760214685$，刚刚好。对于 Sub3,4，将 $n=10^9,A=10^{18}$ 代入显然也是符合要求的。但是有个小问题是 Sub3,4 中的 $n$ 有可能比 $10^9$ 小，它带来的影响是抬高了 $k$ 的上界，此时可能会用到多于 $6$ 个奇数，多一个奇数会使所需询问次数多 $2$，这意味着 $k$ 的上界 $\dfrac{A}{n-1}\ge B\iff n\le \left\lfloor\dfrac{A}{B}\right\rfloor+1=147924297$，也就说如果想要把上界抬高到 $6$ 个奇数无法搞定 $n$ 至少要降至 $147924297< \dfrac{10^9}{4}$，即二分次数至少会减 $2$，因此即使 $n<10^9$ 也不会出事。多两个奇数或更多也是类似的分析。至此我们解决了赛时的限制。

赛后毒瘤 yzy 把次数卡到了 $32$ 次。原本的做法由两部分组成：第一部分是根据事先定好的模数集合用 $12$ 次询问确定合适的模数 $p$，这过程中除了 $k,2b$ 的取值外不会获得任何有效信息，不过这已经很强了，因为它实际上给出了修改前的函数具体长啥样。第二部分是根据已知信息确定拐点位置，我们需要把这部分的次数卡到 $20$。回想最开始在 Sub2 中提到的二分做法，每次询问 $g(1)+g(x)$，然后把它与修改前 $g(1)+g(x)$ 应该是什么做对比，以此推出拐点对于 $x$ 的影响，进而得到拐点与 $x$ 的相对位置。这里固定的 $1$ 看起来很奇怪，因为 $1$ 始终不会受到拐点影响，那么感觉上讲根据 $g(1)+g(x)$ 能得到的信息不如询问 $g(x)+g(y)$。由于拐点会偏移一段后缀，因此 $g(x)+g(y)$ 的偏移量有三种可能：$0,k,2k$，分别对应拐点位于 $[y,r),[x,y),[l,x)$，其中 $[l,r)$ 为当前拐点所在的位置范围。所以把二分改为三等分当前区间，次数由 $\log_2 n$ 变为 $\log_3n$，刚好能通过 Sub5！

对于 Sub4 会遇到与之前同样的问题，也就是若 $n$ 减小导致 $k$ 的上界抬高对询问次数的影响。仍然套用前文的分析，然而 $147924297>\dfrac{10^9}{9}$，看起来有点寄，毕竟在上界抬高到 $6760214685$ 时 $\log_3 n$ 只减小了 $1$，而确定模数时用的询问次数增加了 $2$。幸运的是 $\lfloor\log_3{10^9}\rfloor=18$，换句话说它有 $2$ 次的冗余量，因此不会炸。而之后模数集合的大小不会增加太多，粗略地估计一下，大小每增加 $1$ 其 $\operatorname{lcm} B$ 就会翻至少 $20$ 倍。$n\le \left\lfloor\dfrac{A}{B}\right\rfloor+1$，所以 $n$ 的上界也会减少 $20$ 倍，对应 $\log_3 n$ 会减小 $2$，能够抵消模数集合大小增加 $1$ 对询问次数的影响。

实现时还有个细节是如何尽量三等分区间 $[l,r)$，设三等分点分别为 $x<y$，则 $x-l=y-x=r-y$，解得 $x=\dfrac{2l+r}{3},y=\dfrac{l+2r}{3}$。

代码如下（码 $\LaTeX$ 不易，能不能点个赞再走啊 awa）：

//author:望远星
#include<bits/stdc++.h>
#define pii pair<int,int>
#define fi first
#define se second
#define pb push_back
#define eb emplace_back
#define mk make_pair
#define sml(x,y) (x=min(x,y))
#define big(x,y) (x=max(x,y))
#define ll long long
#define uint unsigned int
#define ull unsigned long long
#define umap unordered_map
#define db double
#define fo(i,x,y) for(int i=(x);i<=(y);++i)
#define go(i,x,y) for(int i=(x);i>=(y);--i)
#define ptc putchar
#define emp emplace
#define re return
//#define int ll 
using namespace std;
ll seed=chrono::system_clock::now().time_since_epoch().count();
mt19937 rnd(seed);
inline int rm(int x,int y){return (int)(rnd()%(y-x+1ll)+x);}
inline int read(){int ch=getchar(),x=0,f=1;while(!isdigit(ch)){if(ch==(int)('-'))f=-1;ch=getchar();}while(isdigit(ch)){x=(x<<1)+(x<<3)+(ch^48);ch=getchar();}return x*f;}
inline void out(int *a,int l,int r){fo(i,l,r) cout<<*(a+i)<<' ';puts("");}

namespace func{
int k=100,b=11111,t=7;
ll F(int x){
    if(t<x) return k*(x-1ll)+b;
    return (ll)k*x+b;
}
//using func::F;
int cnt;

inline int ask(int l,int r,int p){
    printf("? %d %d %d\n",l,r,p);
    cnt++;
    cout.flush();
    return read();
    //printf("%d\n",(F(l)+F(r))%p);
    //if(F(l)==F(r)) return -1;
    //return (F(l)+F(r))%p;
}

void answer(int x){
    printf("! %d\n",x);
    cout.flush();
    if(!read()) exit(0);
    //if(t!=func::t) exit(0);
//    cout<<"cnt="<<cnt<<'\n';    
}
}
using func::answer;
using func::ask;

const int P[]={49,47,45,43,41,37,31,29,25,23};
const int ni[]={25,24,23,22,21,19,16,15,13,12};
int n;

void solve(){
    int L=1,R=read(),q=read(),pp=read();
    if(pp==2){
        int l=1,r=R,mid;
        while(l<=r){
            //printf("[%d,%d]\n",l,r);
            if(r-l<=1){
                answer(l);
                return;
            }
            mid=l+((r-l)>>1);
            //printf("mid=%d\n",mid);
            int x=ask(1,mid,2);
            if(x==-1){
                answer(1);
                return;
            }
            if((mid&1)^(x&1)) l=mid;
            else r=mid;
        }
        re;
    }
    int p=0,k=0,b=0;
    fo(i,0,9){
        p=P[i];
        int x=ask(1,2,p),y=ask(2,3,p);
        if(x==-1){answer(1); re;}
        if(y==-1){answer(2); re;}
        if(x==y) continue;
        k=(y-x+p)*ni[i]%p;
        b=(x-3*k+3*p)%p;
        break;
    }
    while(R-L>1){//对开区间 [l,R) 三等分 
        int x=(2ll*L+R)/3,y=(L+2ll*R)/3;
        //printf("[%d,%d] %d,%d\n",L,R,x,y);
        int w=ask(x,y,p);
        if(w==-1){answer(x);re;}
        int a0=(k*(x-2ll+y)+b)%p,a1=(k*(x-1ll+y)+b)%p,a2=(k*(x+0ll+y)+b)%p;
        if(w==a0) R=x;
        if(w==a1) L=x,R=y;
        if(w==a2) L=y;
    }
    answer(L);
}

signed main(){
    int T=read();
    while(T--) solve();
    return 0;
}