posted on 2022-10-20 13:58:54 | under 题解 | source
有个地方写错了，改一下
problem
Soso 有一个无穷序列 \(\{X_i\}\) 定义如下：
\[X_i=\begin{cases} S,&(i=0)\\ (A\cdot X_{i-1}+B)\bmod P,&(i\geq 1) \end{cases}\]其中 \(0\leq S,A,B<P\leq 10^9\) 均为常数，\(P\in\textrm{Prime}\)。现在求最小的 \(i\) 使得 \(X_i=G\)。多测 \(100\) 组数据。
solution
general
思路：将式子化为只与 \(k\) 有关的东西。
\[\begin{aligned} X_k&=SA^k+BA^{k-1}+BA^{k-2}+\cdots+BA^0\\ &=SA^k+B(A^{k-1}+A^{k-2}+\cdots+A^0)\\ &=SA^k+B\frac{A^k-1}{A-1}\\ &=SA^k+\frac{B}{A-1}A^k-\frac{B}{A-1}\\ &=(S+\frac{B}{A-1})A^k-\frac{B}{A-1}=G. \end{aligned}\]令 \(C=\frac{B}{A-1}\)，欲求 \(A^k\equiv \frac{G+C}{S+C}\pmod P\)，因为 \(P\) 为质数，故使用 BSGS 求得最小的 \(k\)。
special judge
- \(S=G\Rightarrow0\)。
- \(A=0\)：check if \(B=G\) or \(S=G\)。
- \(A=1\)：\(X_n=S+Bn\Rightarrow n=\frac{G-S}{B}\)。
- \(S=B=0\)：\(X_n=0\)。
code
#include <map>
#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>
using namespace std;
typedef long long LL;
LL qpow(LL a,LL b,int p){LL r=1;for(;b;b>>=1,a=a*a%p) if(b&1) r=r*a%p;return r;}
LL inv(LL a,int p){return qpow(a,p-2,p);}
LL bsgs(LL x,LL y,int p){
// fprintf(stderr,"bsgs(%lld,%lld,%d)\n",x,y,p);
if(x%=p,y%=p,y==1||x==y) return y!=1;
//x^(am-b)=(x^m)^a/x^b=y =>(x^m)^a=y*x^b
int m=ceil(sqrt(p));
map<int,int> mp;
for(int i=m;i>=1;i--) mp[qpow(x,i*m,p)]=i*m;
int res=1e9;
for(int i=0;i<=m;i++){
if(mp.count(y*qpow(x,i,p)%p)) res=min(res,mp[y*qpow(x,i,p)%p]-i);
}
return res==1e9?-1:res;
}
LL p,a,b,s,g;
int mian(){
if(s==g) puts("0");
else if(a==0) printf("%lld\n",b==g?1ll:-1ll);
else if(a==1){
if(!b) puts("-1");
else printf("%lld\n",(g-s+p)%p*inv(b,p)%p);
}else{
LL cmb=b*inv(a-1,p)%p;
printf("%lld\n",bsgs(a,(g+cmb)%p*inv(s+cmb,p)%p,p));
}
return 0;
}
int main(){
for(scanf("%*d");~scanf("%lld%lld%lld%lld%lld",&p,&a,&b,&s,&g);mian());
return 0;
}