题解 ABC270G【Sequence in mod P】

· · 题解

有个地方写错了，改一下

problem

Soso 有一个无穷序列 \{X_i\} 定义如下：

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 有关的东西。

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

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;
}