设目标状态为.画一画柿子
令.有
所以题目转化为了求最小的使得
把除过去就能做了,最后答案.
注意下面几个特判
- (这个也可以在几种情况内部判,但放在外面更方便)
- 要求逆元注意特判的情况.
- 详见代码
CODE
#include<bits/stdc++.h>
using namespace std;
typedef long long LL;
inline LL qpow(LL a, LL b, LL c) {
LL re = 1;
while(b) {
if(b & 1) re = re * a % c;
a = a * a % c; b >>= 1;
}
return re;
}
int gcd(int a, int b) { return b ? gcd(b, a%b) : a; }
map<int, int>myhash;
inline int Baby_Step_Giant_Step(int a, int b, int p) {
if(p == 1) return 0;
a %= p, b %= p;
if(b == 1) return 0;
int cnt = 0; LL tmp = 1;
for(int g = gcd(a, p); g != 1; g = gcd(a, p)) {
if(b % g) return -1;
b /= g, p /= g, tmp = tmp * (a/g) % p;
++cnt;
if(b == tmp) return cnt;
}
myhash.clear();
int m = int(sqrt(p) + 1);
LL base = b;
for(int i = 0; i < m; ++i) {
myhash[base] = i;
base = base * a % p;
}
base = qpow(a, m, p);
for(int i = 1; i <= m+1; ++i) {
tmp = tmp * base % p;
if(myhash.count(tmp))
return i*m - myhash[tmp] + cnt;
}
return -1;
}
int main() {
int a, b, x1, xn, p, T;
scanf("%d", &T);
while(T--) {
scanf("%d%d%d%d%d", &p, &a, &b, &x1, &xn);
if(x1 == xn) puts("1");
else if(a == 0) puts(xn == b ? "2" : "-1");
else if(a == 1) {
xn = (xn - x1 + p) % p;
//b*x = Xn (mod p) (t > 0)
if(b == 0) puts("-1");
else printf("%d
", int(1ll * xn * qpow(b, p-2, p) % p)+1);
}
else {
int tmp = 1ll * b * qpow(a-1, p-2, p) % p;
(xn += tmp) %= p, (x1 += tmp) %= p;
//X1 * a^x = Xn (mod p) (x1 != tmp)
if(x1 == 0) puts("-1");
else {
int ans = Baby_Step_Giant_Step(a, 1ll * xn * qpow(x1, p-2, p) % p, p);
if(~ans) printf("%d
", ans+1);
else puts("-1");
}
}
}
}