[BZOJ3122][Sdoi2013]随机数生成器

首先，很容易看出来，这个式子是[秦九韶算法](http://en.wikipedia.org/wiki/Horner’s_method)，不考虑取模的话就是：

\[ X_n=a^{n-1}X_1+b\sum_{k=0}^{n-2}a^k \]

嗯，我们可以套上一个等比数列求和公式，变成

\[ t\equiv a^{n-1}X_1+b\cdot\frac{1-a^{n-1}}{1-a} \pmod{p} \]

乘过去

\[ t\left(1-a\right)\equiv \left[\left(1-a\right)X_1-b\right]a^{n-1}+b \pmod{p} \]

这个时候自然是想再除过来，这里有个很明显的坑应该大家都发现了，就是逆元要存在。

\[ a^{n-1}\equiv\frac{t-ta-b}{\left(1-a\right)X_1-b} \pmod{p} \]

然后就是水水的BSGS了。

特殊情况

我就是傻傻这样，结果发现全部WA了……原因是多组数据、然后特殊情况完全没有考虑到。其实下面的特殊情况列出来会觉得很傻逼，但是我觉得比较需要思考的是：为什么会被特殊数据卡？

当\(a=1\)时： \(\left[X_1+b(n-1)\right]\equiv t \pmod{p}\)，显然就是扩展欧几里得了。为什么这个BSGS会挂呢？原因是：BSGS那个式子用到了等比数列求和，但是显然比为1的数列不是等比数列。

当\(a=0\)时：ans = b == t ? 2 : -1。这个连数列都没了

当\(X_1=t\)时：ans = 1。什么都没了……

所以这题给我最大的启示就是：千万不要轻视细节……

代码

bzoj3122[Sdoi2013]随机数生成器 
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82

#include <cmath>
#include <cstdio>
#include <cstring>
#include <algorithm>

typedef long long Int64;
struct Triple
{
  Int64 x, y, z;
  Triple(const Int64 a, const Int64 b, const Int64 c): x(a), y(b), z(c) { }
};
Triple exgcd(const Int64 a, const Int64 b)
{
  if (!b) return Triple(1, 0, a);
  const Triple last = exgcd(b, a%b);
  return Triple(last.y, last.x - a / b * last.y, last.z);
}
class Hash
{
  static const int HASHMOD = 7679977;
  Int64 k[HASHMOD+100];
  int time[HASHMOD+100], v[HASHMOD+100], timestamp;
  int locate(const Int64 key)
  {
    int h = key%HASHMOD;
    while (time[h] == timestamp && k[h] != key) ++h;
    return h;
  }
public:
  void clear() { ++timestamp; }
  void set(const Int64 key, const int value)
  {
    const int h = locate(key);
    if (time[h] != timestamp) time[h] = timestamp, k[h] = key, v[h] = value;
  }
  int get(const Int64 key)
  {
    const int h = locate(key);
    return time[h] == timestamp ? v[h] : -1;
  }
} hash;
int bsgs(Int64 A, Int64 B, Int64 C)
{
  hash.clear();
  Int64 base = 1, D = 1;
  const int m = static_cast<int>(std::ceil(std::sqrt(C)));
  for (int i = 0; i < m; ++i, base = base*A%C) hash.set(base, i);
  for (int i = 0; i <= m; ++i)
  {
    Triple gcd = exgcd(D, C);
    const int j = hash.get((gcd.x*B%C+C)%C);
    if (j != -1) return i*m+j;
    D = D*base%C;
  }
  return -1;
}

Int64 T, p, a, b, x1, t;
int solve()
{
  scanf("%lld%lld%lld%lld%lld", &p, &a, &b, &x1, &t);
  if (x1 == t) return 1;
  if (a == 0) return b == t ? 2 : -1;
  if (a == 1)
  {
    Triple gcd = exgcd(b, p);
    if (std::abs(gcd.z) != 1) return -1;
    return ((t-x1)/gcd.z*gcd.x%p+p)%p+1;
  }
  const Int64 tmp1 = (1-a)*x1-b;
  const Triple gcd = exgcd(tmp1, p);
  if (std::abs(gcd.z) != 1) return -1;
  const Int64 tmp2 = (t-t*a-b) % p * gcd.x / gcd.z % p;
  const int res = bsgs(a, (tmp2+p)%p, p)+1;
  return res < 1 ? -1 : res;
}
int main()
{
  scanf("%lld", &T);
  while (T--)
    printf("%d\n", solve());
}

Comments