B:generator 1
题意
给你$x_0,x_1,a,b, x_i=ax_{i-1}+bx_{i-2}$让你求出$x_n$
思路
典型的矩阵快速幂,但是n的范围太大,所以得快速幂得用十进制快速幂
#include<bits/stdc++.h>
using namespace std;
#define ll long long
const int maxn = 1e6 + 5;
ll mod;
struct Matrix{
ll mat[2][2];
Matrix() {memset(mat, 0, sizeof(mat));};
void init() {
mat[0][0] = mat[1][1] = 1;
}
void init(ll a, ll b) {
mat[0][0] = 0; mat[0][1] = b;
mat[1][0] = 1; mat[1][1] = a;
}
void operator = (Matrix x) {
for (int i = 0; i <= 1; i ++)
for (int j = 0; j <= 1; j ++)
mat[i][j] = x.mat[i][j];
}
};
void Print(Matrix x) {
for (int i = 0; i <= 1; i ++) {
for (int j = 0; j <= 1; j ++)
cout << x.mat[i][j] << " ";
cout << endl;
}
}
Matrix operator * (Matrix x, Matrix y) {
Matrix t;
for (int i = 0; i <= 1; i ++)
for (int j = 0; j <= 1; j ++)
for (int k = 0; k <= 1; k ++)
t.mat[i][j] = (t.mat[i][j] + x.mat[i][k] * y.mat[k][j]) % mod;
return t;
}
Matrix Ksm(Matrix x, ll b) {
//cout << b << endl;
Matrix t; t.init();
while(b) {
if(b & 1) t = t * x;
x = x * x;
b >>= 1;
}
//Print(t);
return t;
}
int main() {
ll x0, x1, a, b;
scanf("%lld %lld %lld %lld", &x0, &x1, &a, &b);
char s[maxn];
scanf("%s%lld", s, &mod);
int len = strlen(s);
reverse(s, s+len);
Matrix t, ans; t.init(a, b);
ans.mat[0][0] = x0; ans.mat[0][1] = x1;
Matrix res;
res.init();
for (int i = 0; i < len; i ++) {
res = res * Ksm(t, s[i]-'0');
t = Ksm(t, 10);
// Print(res);
// Print(t);
}
ans = ans * res;
printf("%lld\n", ans.mat[0][0]);
return 0;
}
C:generator 2
题意
有这么一个递推式$x_i=(a\cdot x_{i-1}+b)\mod p$,让你求$v$在$[1,n-1]$中第一次出现的位置
思路
因为递推式模$p$,所以$x$的循环节一定小于$p$,
而$x$又是这种形式$x_n=a(a(a(ax+b)+b)+b)+b$
所以我们的任务就变成$A^{m} \equiv v\mod p$求最小的$m$
${A^1=x,A^2=(ax+b),A^3=a(ax+b)+b,A^4=a(a(ax+b)+b)+b)+b}$
而$A^m\equiv v\mod p$明显可以用BSGS
但是BSGS的一个使用条件能不能求出$A^{-i*S}$
但是我们怎么求出$A^{-i*S}$呢
正常的加是乘a加b,那么除就是除a减$\frac{b}{a}$
举个例子:
$x_0=x,x_1=ax+b,x_2=a(ax+b)+b,x_3=a(a(ax+b)+b)+b$
我们从$x_3$降到$x_1$,$x_3$先除$a$再减去$\frac{b}{a}$变成$x_2$,然后再除$a$减去$\frac{b}{a}$变成$x_1$
那我们从$A^{2S+j}$降到$A^{S+j}$只需要进行$S$次操作即可
这样我们就可以用BSGS了
跟BSGS的步骤差不多,我们可以把式子化成 $A^{i*S+j}\equiv v\mod p$
我们可以预处理出来$A^S$ ,然后遍历找到一个$A^j\equiv vA^{-iS}\mod p$
也就是说在这个式子中$A^{-i*S}$不是一个值,而是一种操作,把$v$所代表的次数降下$S$
$x_0=1,x_1=2*1+1,x_2=,x_4=15,x_5=31$
因为我们已经预处理了一个$A^S$,那么在我们遍历$i$的过程中每次降下一个$S$,知道找到或者找不到
用Hash存一下$A^j$
AC代码
#include<bits/stdc++.h>
using namespace std;
#define ll long long
typedef pair<int, int>pis;
const int limit = 1e6;
pis d[limit+6];
int vals[limit+6], pos[limit+6];
int Ksm(ll a, int b, int p) {
ll res = 1;
while(b) {
if(b & 1) res = res * a % p;
a = a * a % p;
b >>= 1;
}
return res;
}
int inv(int a, int p) { return Ksm(a, p-2, p); }
void solve() {
ll n, x0, a, b, p; int Q;
scanf("%lld %lld %lld %lld %lld %d", &n, &x0, &a, &b, &p, &Q);
if(!a) {
while(Q --) {
int v; scanf("%d", &v);
if(v == x0) printf("0\n");
else if(v == b) printf("1\n");
else printf("-1\n");
}
return ;
}
d[0] = {x0, 0};
for (int i = 1; i <= limit; i ++) {
int val = (a*d[i-1].first+b) % p;
d[i] = {val, i};
}
sort(d, d+limit+1);
int cnt = 0;
for (int i = 0; i <= limit; i ++) {
vals[cnt] = d[i].first; pos[cnt++] = d[i].second;
while(d[i].first == d[i+1].first && i+1 <= limit) i++;
}
int inv_a = inv(a, p);
int inv_b = (p-b) % p * inv_a % p;
ll aa = 1, bb = 0;
for (int i = 0; i <= limit; i ++) {
aa = aa * inv_a % p;
bb = (bb * inv_a + inv_b) % p;
}
while(Q --) {
int v; scanf("%d", &v);
int it = lower_bound(vals, vals+cnt, v) - vals;
if(it < cnt && vals[it] == v) {
if(pos[it] < n) printf("%d\n", pos[it]);
else printf("-1\n");
continue;
}
int m = p/(limit+1) + 3, flag = 0;
for (int i = 1; i <= m; i ++) {
v = (aa * v + bb) % p;
it = lower_bound(vals, vals+cnt, v) - vals;
if(it<cnt && vals[it] == v) {
flag = 1;
int res = i*(limit+1)+pos[it];
if(res>=n) res = -1;
printf("%d\n", res);
break;
}
}
if(!flag) printf("-1\n");
}
}
int main() {
int T;
scanf("%d", &T);
while(T --) solve();
return 0;
}