企业官网建设流程全解析

Solution

我们不能直接查询数列前几项，只能查询L≤i<ML\le i<ML≤i<M的位置。这意味着很可能需要利用数列本身的数学结构和性质。

我们需要一个可以让我们从任意靠后的几项推出p,qp,qp,q的性质。

这里直接上结论
fi2−fi−1fi+1≡(−q)i f_i^2-f_{i-1}f_{i+1}\equiv(-q)^ifi2​−fi−1​fi+1​≡(−q)i
不难归纳证明。（专门对着这个式子出的题吧，没学过二阶齐次线性递推做不出来很正常）

最自然的想法是问fM−3,fM−2,fM−1f_{M-3},f_{M-2},f_{M-1}fM−3​,fM−2​,fM−1​。

此时根据结论，有
fM−22−fM−3fM−1≡(−q)M−2 f_{M-2}^2-f_{M-3}f_{M-1}\equiv(-q)^{M-2}fM−22​−fM−3​fM−1​≡(−q)M−2
由费马小定理，(−q)M−2≡(−q)−1(-q)^{M-2}\equiv(-q)^{-1}(−q)M−2≡(−q)−1，因此
q≡−(fM−22−fM−3fM−1)−1 q\equiv-\left(f_{M-2}^2-f_{M-3}f_{M-1}\right)^{-1}q≡−(fM−22​−fM−3​fM−1​)−1
我们就得到了qqq。再来考虑如何得到ppp。

由递推式得
fM−1≡qfM−3+pfM−2pfM−2≡fM−1−qfM−3 \begin{aligned} f_{M-1}&\equiv qf_{M-3}+pf_{M-2} \\ pf_{M-2}&\equiv f_{M-1}-qf_{M-3} \end{aligned}fM−1​pfM−2​​≡qfM−3​+pfM−2​≡fM−1​−qfM−3​​
此时如果fM−2≢0f_{M-2}\not\equiv 0fM−2​≡0我们就做完了。接下来只需要考虑fM−2≡0f_{M-2} \equiv 0fM−2​≡0的情况。

此时仅仅知道fM−3,fM−2,fM−1f_{M-3},f_{M-2},f_{M-1}fM−3​,fM−2​,fM−1​肯定得不出ppp，尝试查询fM−4f_{M-4}fM−4​。

由结论得
fM−32−fM−4fM−2≡(−q)M−3 f_{M-3}^2-f_{M-4}f_{M-2} \equiv(-q)^{M-3}fM−32​−fM−4​fM−2​≡(−q)M−3
由费马小定理和fM−2≡0f_{M-2}\equiv 0fM−2​≡0得
fM−32≡(−q)−2 f_{M-3}^2\equiv(-q)^{-2}fM−32​≡(−q)−2
因此q≡±1fM−3q\equiv\pm \frac{1}{f_{M-3}}q≡±fM−3​1​。

显然fM−3≢0f_{M-3}\not\equiv 0fM−3​≡0（不然整个数列就全000了）。可以放心将解出的两个qqq代入fM−2≡pfM−3+qfM−4f_{M-2}\equiv pf_{M-3}+qf_{M-4}fM−2​≡pfM−3​+qfM−4​解出两个ppp，分别提交即可。

最终交互策略：

Code

#include<iostream>#defineintlonglongusingnamespacestd;intm,l;intquery(intx){intres;cout<<"? "<<x<<endl;cin>>res;returnres;}voidguess(intp1,intq1,intp2,intq2){p1=(p1+m)%m,p2=(p2+m)%m;q1=(q1+m)%m,q2=(q2+m)%m;cout<<"! "<<p1<<' '<<q1<<' '<<p2<<' '<<q2<<endl;}intksm(intx,inty){intres=1;while(y){if(y&1)(res*=x)%=m;(x*=x)%=m,y>>=1;}returnres;}voidsolve(){cin>>m>>l;// f_{m-4}:a// f_{m-3}:b// f_{m-2}:c// f_{m-1}:dintc=query(m-2),b=query(m-3);if(c){intd=query(m-1);intq=-ksm((c*c%m-b*d%m)%m,m-2);intp=(d-q*b)%m*ksm(c,m-2)%m;guess(p,q,p,q);}else{inta=query(m-4);intq=ksm(b,m-2);intp=-q*a%m*ksm(b,m-2)%m;guess(p,q,-p,-q);}}signedmain(){intT;cin>>T;while(T--)solve();return0;}