题意：给你一个数列，a₁ = x，a_i = (A * a_i-1 + B) % P，求第一个是t的是哪一项，或者永远不会有t。

解：循环节不会超过P。我们使用BSGS的思想，预处理从t开始跳√P步的，插入Hash表内。

然后每次把a₁跳√P步，来看是否在Hash表中存在。

这样发现我们有40，WA了60分。为什么呢？考虑是否存在两个数x和y，它们跳一次之后一样了。发现这种情况只会出现在A = 0的时候，于是特判掉A = 0。可获得100分。

1 #include 
      
         2   3 const int N = 100010;  4   5 int MO, A, B, op, aim;  6   7 inline int qpow(int a, int b) {  8     int ans = 1;  9     while(b) { 10         if(b & 1) { 11             ans = 1ll * ans * a % MO; 12         } 13         a = 1ll * a * a % MO; 14         b = b >> 1; 15     } 16     return ans; 17 } 18  19 namespace Hash { 20     struct Node { 21         int nex, v, id; 22     }node[N]; int tp; 23     const int mod = 999983; 24     int e[mod]; 25     inline void clear() { 26         tp = 0; 27         memset(e, 0, sizeof(e)); 28         return; 29     } 30     inline void insert(int v, int id) { 31         int x = v % mod; 32         for(int i = e[x]; i; i = node[i].nex) { 33             if(node[i].v == v) { 34                 node[i].id = id; 35                 return; 36             } 37         } 38         node[++tp].nex = e[x]; 39         node[tp].v = v; 40         node[tp].id = id; 41         e[x] = tp; 42         return; 43     } 44     inline int find(int v) { 45         int x = v % mod; 46         for(int i = e[x]; i; i = node[i].nex) { 47             if(node[i].v == v) { 48                 return node[i].id; 49             } 50         } 51         return -1; 52     } 53 } 54  55 inline void solve() { 56     Hash::clear(); 57     scanf("%d%d%d%d%d", &MO, &A, &B, &op, &aim); 58     if(op == aim) { 59         printf("%d\n", 1); 60         return; 61     } 62     if(A == 0) { 63         if(B == aim) { 64             printf("2\n"); 65         } 66         else { 67             printf("-1\n"); 68         } 69         return; 70     } 71     int T = sqrt((double)MO); 72     for(int i = 0; i < T; i++) { 73         Hash::insert(aim, i); 74         //printf("Hash insert %d %d \n", aim, i); 75         aim = (1ll * A * aim % MO + B) % MO; 76     } 77     int c = qpow(A, T), d; 78     if(A == 1) { 79         d = 1ll * B * T % MO; 80     } 81     else { 82         d = (1ll * (c - 1) * qpow(A - 1, MO - 2) % MO * B % MO + MO) % MO; 83     } 84     //printf("c = %d d = %d \n", c, d); 85     for(int i = 1; (i - 1) * T < MO; i++) { 86         op = (1ll * op * c + d) % MO; 87         int t = Hash::find(op); 88         //printf("op = %d  t = %d \n", op, t); 89         if(t != -1) { 90             printf("%d\n", i * T - t + 1); 91             return; 92         } 93     } 94     printf("-1\n"); 95     return; 96 } 97  98 int main() { 99     int T;100     scanf("%d", &T);101     while(T--) {102         solve();103     }104     return 0;105 }