题目大意
给定a, b, p, t, [latex]X_1[/latex]。
问数列 [latex] \{X_{i}\}, X_i = (a \times X_{i-1}+b) % p [/latex] 的第几项为t
附赠测试数据一组!
Input:
10
11 1 4 0 7
7 4 8 2 4
7 5 1 5 1
7 1 2 5 6
13 1 2 3 2
17 1 2 6 5
7 6 1 7 4
5 2 7 5 4
3 1 2 2 2
23 1 1 3 4
Output:
11
-1
-1
5
7
9
-1
4
1
2
解题报告
首先推出{Xn}通项
$$ {Xn}=a^{n-1}+b(a^0+a^1+a^2+…+a^{n-1}) $$
带入t得到
$$ a^{n-1}+b(a^0+a^1+a^2+…+a^{n-1}) \equiv t \pmod p $$
化简
$$ a^{n-1}+b\frac{a^{n-1}-1}{a-1} \equiv t \pmod p $$
$$ (a-1)a^{n-1}+ba^{n-1}-b \equiv t(a-1) \pmod p $$
$$ ((a-1)+b)a^{n-1} \equiv (t(a-1)+b) \pmod p $$
$$ a^{n-1} \equiv (t(a-1)+b)((a-1)+b)^{-1} \pmod p $$
然后发现这就是个离散对数。。默写一下BSGS
最后进行特判a=0,1和b=0,1的情况,a=1时直接解线性同余方程,其他的都比较简单不说了。
最后吐槽: 扩展欧几里得求逆元时没有特判无解。。卡我一个小时%>_<%要吐血了……
代码
#include <cstdio>
#include <cstring>
#include <cstdlib>
#include <algorithm>
#include <cmath>
typedef long long LL;
void exgcd (LL a, LL b, LL & x, LL & y, LL & d) {
if(b == 0) {
x = 1, y = 0, d = a;
return ;
}
exgcd(b, a%b, x, y, d);
LL t = x; x = y; y = t-a/b*y;
}
//Ax = B (mod P)
const LL NOSOL = -193718391378LL;
LL linerCT(LL A, LL B, LL P) {
LL X, Y, D;
exgcd(A, P, X, Y, D);
if(B % D) return NOSOL;
B /= D; X = ((X*B%P)+P) % P;
return X;
}
LL advPow (LL a, int b, LL c) {
a %= c;
LL ret = 1;
while(b) {
if(b & 1) ret *= a, ret %= c;
a *= a;
a %= c;
b >>= 1;
}
return ret;
}
#include <map>
std :: map<int, int> mp;
//A^x = B (mod C)
LL BSGS (LL A, LL B, LL C) {
A %= C;
if(!A) {
if(B == 0) return 1;
else return NOSOL;
}
mp.clear();
LL i = 1, r = sqrt(C)+1; mp[1] = 0;
for(LL t = A%C; i<r; i++, (t*=A)%=C)
if(mp.find(t) == mp.end()) mp[t] = i;
LL D = 1, T = advPow(A, C-1-r, C);
for(int i = 0; i<r; i++) {
if(mp.find(D*B%C) != mp.end())
return mp[D*B%C] + i*r;
D = D*T%C;
}
return NOSOL;
}
#include <iostream>
int main () {
int cas;
scanf("%d", &cas);
while(cas --) {
LL P, a, b, X, t;
std :: cin >> P >> a >> b >> X >> t;
if(X == t) puts("1");
else if(a == 0) {
if(b == t) puts("2");
else puts("-1");
} else if(a == 1) {
LL C=(t-X+P)%P,x,y;
LL t; exgcd(b,P,x,y,t);
if(C%t){puts("-1"); continue ;}
C/=t;x=x*C%P;
if(x<0)x+=P;
std :: cout << x+1 << '\n';
} else {
LL r = linerCT((X*((a-1+P)%P) + b)%P, 1, P);
if(r == NOSOL) {puts("-1"); continue ;}
LL right = (t*(a-1+P)%P + b)%P*r% P;
LL ans = BSGS(a, right, P);
if(ans == NOSOL) ans = -2;
std :: cout << ans+1 << '\n';
}
}
}
Join the discussion