【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}$，所以乘法取模需要使用一些科技。

代码

#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);
}