牛客多校第五场 —— generator 2 BSGS

题目链接：点我啊╭(╯^╰)╮

题目大意：

    给定$n,x_0,a,b,p$，有递推式 $x_i=(a?x_{i?1}+b)\%p$
    有 $Q$ 个询问，每次询问给定一个 $v$，问是否存在一个最小的 $i$ 使得$x_i=v,i\in [0,n?1]$成立
    $1\le n\le 1e18,0\le x_p,a,b,p\le 1e9+7,Q\le 1000,p是质数$

解题思路：

    写出通项：
                                              
    转换成：
                                                       

    则变成了 BSGS 的模板题，唯一不同的是查询量较大
    若对于每一个查询都采用原本的 $O(\sqrt{p})$ 时间复杂度的话，明显不妥
    考虑 BSGS 的本质为打表，那么牺牲打表时间来优化查询时间即可！！

    对于$x^k=y(modp)$
    设 $k=am?b,a\in [1,\frac{p}{m}],b\in [0,m]$
    考虑将 $m$ 设为 $1e3$，那么对于每个询问查询时的复杂度就是 $1e3$ 了

    最后时间复杂度为$O(1e6+q?(1e3+logp))$
    这里手写了哈希，这个板子里最好还是要手写

核心：BSGS的灵活运用

#include<bits/stdc++.h>
#define rint register int
#define deb(x) cerr<<#x<<" = "<<(x)<<'\n';
//#pragma GCC optimize(3,"Ofast","inline")
using namespace std;
typedef long long ll;
using pii = pair <ll,int>;
int T;struct HashTable{static const int HashMod = 123456;struct Line{int u,v,next;} e[1000010];int h[HashMod], cnt;void add(int u,int v,int w){e[++cnt]=(Line){w,v,h[u]};h[u]=cnt;}void clear(){memset(h,0,sizeof(h)); cnt=0;}void insert(int x, int i){int k = x % HashMod;add(k, i, x);}int query(int x){for(int i=h[x%HashMod];i;i=e[i].next)if(e[i].u==x) return e[i].v;return -1;}
} Hash;ll qpow(ll a, ll b, ll p){ll ret = 1;while(b){if(b & 1) ret = ret * a % p;a = a * a % p;b >>= 1;}return ret;
}int main() {scanf("%d", &T);while(T--){ll n, x0, a, b, p, v, q, ans;scanf("%lld%lld%lld%lld%lld", &n, &x0, &a, &b, &p);ll mu = (a*x0%p - x0 + b + p) % p;mu = qpow(mu, p-2, p) % p;ll x = qpow(a, 1001, p), s = 1;Hash.clear();for(int i=1; i<=1e6; i++){s = s * x % p;ll hash = Hash.query(s);if(hash==-1) Hash.insert(s, 1001*i);}scanf("%lld", &q);while(q--){scanf("%lld", &v);if(a == 0){if(v == x0) puts("0");else if(v == b) puts("1");else puts("-1");continue;}if(a == 1){ans = (v - x0 + p) % p * qpow(b, p-2, p) % p;if(ans < n) printf("%lld\n", ans);else puts("-1");continue;}v = (v * (a - 1) % p + b) % p * mu % p;s = v, ans = p + 1;for(int i=0; i<=1001; i++){ll hash = Hash.query(s);s = s * a % p;if(hash == -1) continue;ans = min(ans, hash - i);}if(ans==p+1 || ans>=n) puts("-1");else printf("%lld\n", ans);}}
}