ICPC2019 西安邀请赛 I.Cracking Password
题目链接
https://nanti.jisuanke.com/t/39276
题目大意
给你一个长度为 $n$ 的数列 $b$，问是否存在一对 $a$ 和 $p$ 使得这个数列是数列 $a_i = a ^ i \mod p$ 的一段连续子序列。要求 $p$ 是质数。
题目分析
对于给你的数列 $b$ ，那么对于任意连续的三个数 $x, y, z$ 那么有 $y = ax, z=a^2x$，所以有 $xz = y ^ 2$ 。那么 $y ^ 2 – xz$ 一定是 $p$ 的倍数。所以找到一组 $y ^ 2 – xz \neq 0$ 的连续的三个数。如果全是 $0$ 的话那么就是 $unsure$ 。找到一组之后，将这个差值分解质因数，对于每个质数，可以通过前两个数计算出 $a$ 。随后可以验证这组求出来的 $a$ 和 $p$ 是否满足题意。对于第一个数 $x$，它一定有 $a ^ t \mod p = x$ ，对于使用离散对数求解即可。注意如果所有的数相同，那么只有全是 $1$ 的时候才是 $unsure$ ，否则是 $error$。
代码
#include <iostream>
#include <cstdio>
#include <cstdlib>
#include <cmath>
#include <cstring>
#include <string>
#include <algorithm>
#include <map>
using namespace std;
const int maxn = 1e5 + 5;
long long n;
long long b[maxn];
long long a, p;
int read(){
int x;
scanf("%d", &x);
return x;
}
long long mul(long long x, long long y){
long long ret = 0;
long long k = x / 10000000ll;
ret = (ret + 10000000ll * y % p * k % p) % p;
x %= 10000000ll;
ret = (ret + x * y) % p;
return ret;
}
long long qpow(long long b, long long x){
long long ret = 1;
while(x){
if(x & 1){
ret = mul(ret, b) % p;
}
b = mul(b, b) % p;
x >>= 1;
}
return ret;
}
long long dis_log(long long a, long long b){
long long n = (long long)sqrt(p + .0) + 1;
map <long long, long long> vals;
long long an = 1;
for(long long i=0;i<n;i++){
an = mul(an, a);
}
for(long long i=1,cur=an;i<=n;i++){
if(!vals.count(cur)){
vals[cur] = i;
}
cur = mul(cur, an);
}
for(long long i=0,cur=b;i<=n;i++){
if(vals.count(cur)){
long long ans = vals[cur] * n - i;
if(ans < p){
return ans;
}
}
cur = mul(cur, a);
}
return -1;
}
bool check(){
int i, j;
for(i=1;i<=n;i++){
if(b[i] >= p)return false;
}
for(i=1;i<n;i++){
if(a * b[i] % p != b[i + 1]){
return false;
}
}
if(dis_log(a, b[1]) == -1){
return false;
}
return true;
}
bool solve(int x){
long long i, j;
long long y;
long long t;
y = abs(b[x - 1] * b[x + 1] - b[x] * b[x]);
t = sqrt(y) + 1;
for(p=2;p<=t;p++){
if(y % p == 0){
while(y % p == 0){
y /= p;
}
if(b[x] % __gcd(b[x - 1], p))continue;
a = b[x] * qpow(b[x - 1], p - 2) % p;
if(check()){
return true;
}
}
}
if(y > 1){
p = y;
while(y % p == 0){
y /= p;
}
if(b[x] % __gcd(b[x - 1], p))return false;
a = b[x] * qpow(b[x - 1], p - 2) % p;
if(check()){
return true;
}
}
return false;
}
int main(){
int i, j;
int x = -1;
bool flag = false;
n = read();
for(i=1;i<=n;i++){
b[i] = read();
if(i > 1)flag |= (b[i] != b[i - 1]);
}
if(n == 1){
printf("unsure\n");
return 0;
}
for(i=2;i<n;i++){
if(b[i - 1] * b[i + 1] != b[i] * b[i]){
x = i;
break;
}
}
if(x == -1){
if(flag or b[1] == 1){
printf("unsure\n");
}else{
printf("error\n");
}
}else{
if(solve(x)){
printf("%lld %lld\n", a, p);
}else{
printf("error\n");
}
}
return 0;
}