题目链接: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);
}