2019ICPC西安邀请赛 I. Cracking Password

May 26, 2019 由 小羊

题目链接：计蒜客

题目意思是，已有 $a, p$ 两个数字，给出 $\lbrace a^k \mod p \rbrace$ 这个数列中的连续几项，问是否能够求出 $a, p$，是不存在，一解，还是多解？

首先先来枚举 $p$ 咯。我们可以发现，$p | b_{i-1}b_{i+1}-b_i^2$。于是枚举这些gcd的质因数，然后判断是否有对应的a存在。

如果 $n$ 只有一个，显然是unsure的。

如果这个数列完全为不相等的等比数列，那么由于模数任取，总可以找到一个模数符合要求并且其原根的某个幂次为 $a$，显然我们能给出无穷多组构造，是unsure的。

如果这个数列全部相等，如果为全 $1$ 则unsure，如果全 非$1$ 则error。

如果 $n$ 有两个，那么也可以根据上面两条的得出类似unsure的结论。

最后的坑点在于，是否已知的数字在那个真实的数列里。例如 $n=3, b=\lbrace3, 6, 5\rbrace$，直接计算可以得到$a=2, p=7$，但是数列却是 $\lbrace 2, 4, 1 \rbrace$，所以也应当是error，利用离散对数判断一下即可。

#include <bits/stdc++.h>
using namespace std;
typedef long long lld;
const int MAXN = 1e5+5;
lld b[MAXN], n, maxb = 0, minb = 100000000000;
int pri[MAXN], pcn;
bool isnp[MAXN];

lld gcd(lld a, lld b) { return b ? gcd(b, a % b) : a; }

lld mul(lld a, lld b, lld p)
{
    __int128 aa = a;
    aa *= b;
    aa %= p;
    return lld(aa);
}

lld fpow(lld a, lld n, lld p)
{
    lld b = 1;
    assert(n >= 0);

    while (n)
    {
        if (n & 1) b = mul(b, a, p);
        a = mul(a, a, p);
        n >>= 1;
    }

    return b;
}

lld bsgs(lld a, lld b, lld p)
{
    map<lld,lld> treemap;
    lld m = ceil(sqrt(p+0.5));
    a %= p, b %= p;
    lld inva = fpow(a, m, p);

    for (lld i = 0, ans = b; i <= m; i++)
    {
        ans = i==0 ? b : mul(ans, a, p);
        treemap[ans] = i;
    }

    for (lld i = 1, ans = 1; i <= m; i++)
    {
        ans = mul(ans, inva, p);
        if (treemap.count(ans))
        {
            lld ret = i * m - treemap[ans];
            ret = (ret % p + p) % p;
            return ret;
        }
    }

    return -1;
}

pair<lld,lld> solve(lld p)
{
    lld f = fpow(b[0], p-2, p);
    lld a = mul(b[1], f, p);
    for (int i = 2; i < n; i++)
        if (b[i] != mul(b[i-1], a, p))
            return make_pair(-1, -1);
    if (bsgs(a, b[0], p) == -1)
        return make_pair(-1, -1);
    return make_pair(a, p);
}

void init_prime()
{
    for (int i = 2; i < MAXN; i++)
    {
        if (!isnp[i]) pri[pcn++] = i;
        for (int j = 0; j < pcn; j++)
        {
            int k = i * pri[j];
            if (k >= MAXN) break;
            isnp[k] = true;
            if (i % pri[j] == 0) break;
        }
    }
}

int main()
{
    init_prime();
    scanf("%lld", &n);

    for (int i = 0; i < n; i++)
    {
        scanf("%lld", &b[i]);
        maxb = max(maxb, b[i]);
        minb = min(minb, b[i]);
    }

    if (n == 1)
    {
        printf("unsure\n");
    }
    else if (n == 2)
    {
        if (b[0] == b[1] && b[0] != 1)
        {
            // for the sequence should be part of a^n,
            // so this will not be legal.
            printf("error\n");
        }
        else
        {
            printf("unsure\n");
        }
    }
    else
    {
        set<lld> possibleP;
        lld wtf = 0;
        for (int i = 2; i < n; i++)
            wtf = abs(gcd(b[i] * b[i-2] - b[i-1] * b[i-1], wtf));

        for (int i = 0; i < pcn; i++)
        {
            if (1ll * pri[i] * pri[i] > wtf) break;

            if (wtf % pri[i] == 0)
            {
                if (pri[i] > maxb) possibleP.insert(pri[i]);
                while (wtf % pri[i] == 0) wtf /= pri[i];
            }
        }

        if (wtf > maxb) possibleP.insert(wtf);

        if (possibleP.empty())
        {
            if (!wtf && minb == maxb)
            {
                // all equal, look at 1
                printf(minb != 1 ? "error\n" : "unsure\n");
            }
            else
            {
                // does all gcd equals to 0?
                printf(wtf ? "error\n" : "unsure\n");
            }
        }
        else
        {
            vector<pair<lld,lld>> ans;
            for (auto i : possibleP)
            {
                auto res = solve(i);
                if (res.first != -1)
                    ans.push_back(res);
            }

            if (ans.empty())
            {
                // seems that p exists but no a exists
                printf("error\n");
            }
            else if (ans.size() > 1)
            {
                // many pairs of answers
                printf("unsure\n");
            }
            else
            {
                printf("%lld %lld\n", ans[0].first, ans[0].second);
            }
        }
    }

    return 0;
}