题意
给你个随机数生成器 \(f(x) = a*f(x-1)+b (\mod p)\), 给你初始信息 \(a,b,t,p,f(1)\), 问你几次等于 \(t\), 如果不等于输出 \(-1\).
题解
- \[f(n) = a*f(n-1)+b\]
- \[f(n) = c*a^{
- n-1
- } + \frac {
- b(a^n-1)
- }{
- a-1
- } \text {
- where c is an arbitrary parameter
- } \]
不过上面这个式子咱推不出来, 考虑矩阵乘法
\[\begin{pmatrix} a&b\0&1 \end{pmatrix}^x \times \begin{pmatrix} f(1)\1 \end {pmatrix} = \begin{pmatrix} t\1 \end{pmatrix}\]
我们考虑一个 BSGS 用到矩阵上, 就把他做了.
如果你要用这个式子的话
\[a^{i\sqrt{p} + k} = b (\mod p) \]
前面那个转移矩阵的逆矩阵是
\[\begin{pmatrix} \frac{1}{a}&-\frac{b}{a}\0&1 \end{pmatrix} \]
但我懒得用用逆矩阵, 直接用下面的这个式子.
\[a^{i\sqrt{p} - k} = b (\mod p) \]
带了矩阵常数贼大, 我还懒得手写 hashtable, 吸着氧过了.
估计思路这么清 (zhi) 奇(zhang)的人没几个吧.
- #include<bits/stdc++.h>
- using namespace std;
- int p;
- int inc(int a,int b) {
- a+=b;
- return a>=p?a-p:a;
- }
- int dec(int a,int b) {
- a-=b;
- return a<0?a+p:a;
- }
- int mul(int a,int b) {
- return 1LL*a*b%p;
- }
- struct qwq {
- int r,c;
- int a[3][3];
- qwq(){
- memset(a,0,sizeof a);
- r=c=0;
- }
- qwq operator * (const qwq& rhs) const {
- qwq ret;
- ret.r = r,ret.c = rhs.c;
- for(int i=1;i<=r;++i) {
- for(int j=1;j<=rhs.c;++j) {
- for(int k=1;k<=c;++k) {
- ret.a[i][j]=inc(ret.a[i][j],mul(a[i][k],rhs.a[k][j]));
- }
- }
- }
- return ret;
- }
- bool operator <(const qwq& rhs) const {
- if(r!=rhs.r) return r<rhs.r;
- if(c!=rhs.c) return c<rhs.c;
- for(int i=1;i<=r;++i)
- for(int j=1;j<=c;++j)
- if(a[i][j]!=rhs.a[i][j])
- return a[i][j]<rhs.a[i][j];
- return 0;
- }
- };
- int T,a,b,x1,t,ans;
- qwq qpow(qwq a,int b) {
- assert(b>=0);
- qwq ret;
- ret.r=a.r,ret.c=a.c;
- for(int i=1;i<=ret.r;++i) ret.a[i][i]=1;
- while(b) {
- if(b&1) ret=ret*a;
- a = a * a;
- b>>=1;
- }
- return ret;
- }
- bool BSGS(void) {
- map<qwq,int> M;
- M.clear();
- int lmt = sqrt(p)+1;
- ans = 0x3f3f3f3f;
- qwq base;
- base.a[1][1]=a,base.a[1][2]=b,base.a[2][2]=1;
- base.r=base.c=2;
- qwq fn;
- fn.r=2,fn.c=1;
- fn.a[1][1]=t,fn.a[2][1]=1;
- qwq st;
- st.r=2,st.c=1;
- st.a[1][1]=x1,st.a[2][1]=1;
- qwq step = qpow(base,lmt);
- for(int i=1;i<=lmt+1;++i) {
- st = step*st;
- if(!M.count(st)) {
- M[st]=i;
- }
- }
- bool flag = 0;
- for(int i=0;i<=lmt;++i) {
- if(i) fn = base*fn;
- if(M.count(fn)) {
- flag = 1;
- ans = min(ans,M[fn]*lmt-i);
- }
- }
- return flag;
- }
- int main() {
- scanf("%d",&T);
- while(T--) {
- scanf("%d%d%d%d%d",&p,&a,&b,&x1,&t);
- if(a==0) {
- if(x1==t)
- puts("1");
- else {
- if(b==t) {
- puts("2");
- }
- else {
- puts("-1");
- }
- }
- }
- else {
- if(BSGS()) {
- printf("%d\n",ans+1);
- }
- else {
- puts("-1");
- }
- }
- }
- return 0;
- }
来源: http://www.bubuko.com/infodetail-3099727.html