【2019西安邀请赛I】Cracking Password

题意

选择一个正整数 $a$ 和一个素数 $p$ 用来生成一个密码序列，$a^1 \mod p, a^2 \mod p, a^3 \mod p, \cdots$，给出这个序列的一部分 $b_1, b_2, \cdots, b_n$，求 $a$ 和 $p$ 的值，或判定无解或多解。

思路

这题在现场基本想到正解了QAQ

如果答案存在，那么 $p$ 一定是 $\gcd_{i = 2}^{n - 1}(b_{i - 1} b_{i + 1} - b_i ^ 2)$ 的某个质因子，枚举一下。
这样可以根据相邻的两项计算 $a$ 的值，再遍历一遍检查是否符合。同时要计算 $b_1$ 的离散对数来判断是否可以由 $a$ 得到（而不是判断循环节内是否存在 $a$，因为可能不存在循环节）。

例如：${3, 6, 5}$，不可以由 $a = 2$, $p = 7$ 得到。

特别地，如果所有的数都一样，全 $1$ 则是不确定，其它情况则是错误。

由于 $p$ 高达 $10 ^ {10}$，所以乘法取模需要使用一些科技。

代码

   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
 83
 84
 85
 86
 87
 88
 89
 90
 91
 92
 93
 94
 95
 96
 97
 98
 99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll exgcd(ll a, ll b, ll& x, ll& y)
{
    ll d = a;
    if (b)
        d = exgcd(b, a % b, y, x), y -= x * (a / b);
    else
        x = 1, y = 0;
    return d;
}

vector<ll> getPrimes(ll x)
{
    if (x < 2) return {};
    vector<ll> result;
    for (ll i = 2; i * i <= x; i++)
    {
        if (x % i == 0)
        {
            result.push_back(i);
            do
            {
                x /= i;
            } while (x % i == 0);
        }
    }
    if (x > 1) result.push_back(x);
    return result;
}

ll inv(ll a, ll m)
{
    ll x, y;
    ll d = exgcd(a, m, x, y);
    return d == 1 ? (x + m) % m : -1;
}

inline ll Mul(ll a, ll b, ll m)
{
    if (m <= 1000000000)
        return a * b % m;
    else if (m <= 1000000000000ll)
        return (((a * (b >> 20) % m) << 20) + (a * (b & ((1 << 20) - 1)))) % m;
    else
    {
        ll d = (ll)floor(a * (long double)b / m + 0.5);
        ll ret = (a * b - d * m) % m;
        if (ret < 0) ret += m;
        return ret;
    }
}

ll Pow(ll a, ll n, ll p)
{
    ll t = 1;
    for (; n; n >>= 1, a = Mul(a, a, p))
        if (n & 1) t = Mul(t, a, p);
    return t;
}

ll exbsgs(ll a, ll b, ll p)
{
    if (b == 1LL) return 0;
    ll t, d = 1, k = 0;
    while ((t = __gcd(a, p)) != 1)
    {
        if (b % t) return -1;
        ++k, b /= t, p /= t, d = Mul(d, (a / t), p);
        if (b == d) return k;
    }
    unordered_map<ll, ll> dic;
    ll m = ceil(sqrt(p));
    ll a_m = Pow(a, m, p), mul = b;
    for (ll j = 1; j <= m; j++) mul = Mul(mul, a, p), dic[mul] = j;
    for (ll i = 1; i <= m; i++)
    {
        d = Mul(d, a_m, p);
        if (dic[d]) return i * m - dic[d] + k;
    }
    return -1;
}

const int N = 1 << 17;
int n;
int arr[N];

void quitf(const char* msg)
{
    puts(msg);
    exit(0);
}

ll check(ll p)
{
    for (int i = 0; i < n; i++)
        if (arr[i] >= p) return 0;
    ll x = Mul(arr[1], inv(arr[0], p), p);
    assert(~x);
    if (!~exbsgs(x, arr[0], p)) return 0;
    for (int i = 1; i < n - 1; i++)
        if (Mul(arr[i], x, p) != arr[i + 1]) return 0;
    return x;
}

void judge()
{
    for (int i = 1; i < n; i++)
        if (arr[i] != arr[0]) return;
    if (arr[0] == 1) quitf("unsure");
    quitf("error");
}

int main()
{
    scanf("%d", &n);
    for (int i = 0; i < n; i++) scanf("%d", arr + i);
    if (n == 1) quitf("unsure");
    ll a, p = 0;
    judge();
    for (int i = 1; i < n - 1; i++)
    {
        ll x = ll(arr[i - 1]) * arr[i + 1], y = ll(arr[i]) * arr[i];
        p = __gcd(p, abs(x - y));
    }
    if (!p) quitf("unsure");
    auto factors = getPrimes(p);
    p = 0;
    for (auto& pp : factors)
    {
        ll x = check(pp);
        if (!x) continue;
        if (p) quitf("unsure");
        a = x, p = pp;
    }
    if (!p) quitf("error");
    printf("%lld %lld\n", a, p);
}