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