题意：给你一个数列，a = x，a = (A * a + B) % P，求第一个是t的是哪一项，或者永远不会有t。
解：循环节不会超过P。我们使用BSGS的思想，预处理从t开始跳√P步的，插入Hash表内。
然后每次把a跳√P步，来看是否在Hash表中存在。
这样发现我们有40，WA了60分。为什么呢？考虑是否存在两个数x和y，它们跳一次之后一样了。发现这种情况只会出现在A = 0的时候，于是特判掉A = 0。可获得100分。
#include <bits/stdc++.h>
const int N = ;
int MO, A, B, op, aim;
inline int qpow(int a, int b) {
int ans = ;
while(b) {
if(b & ) {
ans = 1ll * ans * a % MO;
}
a = 1ll * a * a % MO;
b = b >> ;
}
return ans;
}
namespace Hash {
struct Node {
int nex, v, id;
}node[N]; int tp;
const int mod = ;
int e[mod];
inline void clear() {
tp = ;
memset(e, , sizeof(e));
return;
}
inline void insert(int v, int id) {
int x = v % mod;
for(int i = e[x]; i; i = node[i].nex) {
if(node[i].v == v) {
node[i].id = id;
return;
}
}
node[++tp].nex = e[x];
node[tp].v = v;
node[tp].id = id;
e[x] = tp;
return;
}
inline int find(int v) {
int x = v % mod;
for(int i = e[x]; i; i = node[i].nex) {
if(node[i].v == v) {
return node[i].id;
}
}
return -;
}
}
inline void solve() {
Hash::clear();
scanf("%d%d%d%d%d", &MO, &A, &B, &op, &aim);
if(op == aim) {
printf("%d\n", );
return;
}
if(A == ) {
if(B == aim) {
printf("2\n");
}
else {
printf("-1\n");
}
return;
}
int T = sqrt((double)MO);
for(int i = ; i < T; i++) {
Hash::insert(aim, i);
//printf("Hash insert %d %d \n", aim, i);
aim = (1ll * A * aim % MO + B) % MO;
}
int c = qpow(A, T), d;
if(A == ) {
d = 1ll * B * T % MO;
}
else {
d = (1ll * (c - ) * qpow(A - , MO - ) % MO * B % MO + MO) % MO;
}
//printf("c = %d d = %d \n", c, d);
for(int i = ; (i - ) * T < MO; i++) {
op = (1ll * op * c + d) % MO;
int t = Hash::find(op);
//printf("op = %d t = %d \n", op, t);
if(t != -) {
printf("%d\n", i * T - t + );
return;
}
}
printf("-1\n");
return;
}
int main() {
int T;
scanf("%d", &T);
while(T--) {
solve();
}
return ;
}AC代码