2019牛客暑期多校训练营（第五场）C

给定\(n,x_0,a,b,p\)，有递推式\(x_i = (a \cdot x_{i-1} +b)\%p\)。
有\(Q\)个询问，每次询问给定一个\(v\)，问是否存在一个最小的\(i\)使得\(x_i=v,i\in[0,n-1]\)成立
\(1\le n\le 1e18,0\le x_p,a,b<p\le 1e9+7,Q\le 1000,p\)是质数

大步小步(BSGS)学习：https://oi-wiki.org/math/bsgs/

刘汝佳白书数论中也有入门讲解

如果直接看递推式找不到关系可以先列出前几项

\(x_0 = x_0\quad x_1=ax_0+b\quad x_2=a^2x_0+ab+b\quad x_3=a^3x_0+a^2b+ab+b\)

\(x_4=a^4x_0+\sum_{i=0}^3a^ib\quad x_5=a^5x_0+\sum_{i=0}^4a^ib\quad x_6=a^6x_0+\sum_{i=0}^5a^ib\quad x_7=a^7x_0+\sum_{i=0}^6a^ib\)

\(\cdots\)

在BSGS中，\(a^x\equiv b\pmod p\)的求解是前求出前\(m\)项(\(m\)通常取\(\sqrt p\))的答案（即\(a^i\%p,i\in[0,m]\))，存在一个数组中便于查询（值和位置一般都要存）,然后再从\([m+1,2m]\)中找答案，如果这一层中有答案那么也就是说\(a^{i+m} \equiv b\pmod p,i+m\in [m+1,2m])\)可以发现如果把指数上的\(m\)挪到右边，也就是相当于右侧乘了一个\(a^m\)的逆元，式子变成了\(a^i\equiv b\cdot a^{-m}\pmod p\)，所以我们在考虑第二层中是否有答案时，只需要将\(b\)先成一次\(a^m\)的逆元，然后再从我们预处理出来的第一层的答案中寻找是否有解即可。

那么这个题该怎么像上面这个进行一样的操作呢？

我们观察一下，考虑完上一层之后接着考虑下一层的时候，给b乘\(a^m\)的逆元操作意味着什么？该操作可以理解为是除以\(a^m\)，也就是将乘了\(m\)次\(a\)的操作复原了。基于复原思想，如何复原到m次操作之前的结果呢？

回看之前列出来的前8项，假设一层有4个，那么复原就相当于是将\(x_4\)变回\(x_0\)。

\[a^4x_0+a^3b+a^2b+ab+b \rightarrow x_0
\]

\[{a^4x_0+a^3b+a^2b+ab+b \over a^4} = x_0+\frac ba +\frac b{a^2}+\frac b{a^3}+\frac b{a^4}
\]

如果还看不出来，在列一下下一个

\[a^5x_0+a^4b+a^3b+a^2b+ab+b \rightarrow ax_0+b
\]

\[{a^5x_0+a^4b+a^3b+a^2b+ab+b \over a^4} = (ax_0+b)+\frac ba +\frac b{a^2}+\frac b{a^3}+\frac b{a^4}
\]

显然，先除以\(a^4\)，然后再减去\(\frac ba +\frac b{a^2}+\frac b{a^3}+\frac b{a^4}\)即可。

其他处理就几乎和BSGS入门题一样了。

该题如果每次查询\(O(\sqrt p)\)的话会超时，所以我们通过加大预处理的范围去降低时间复杂度。（更多的部分是可以直接算出来存到数组里面的）采取\(O(\sqrt {Qp})\)也就是1e6的大小。

代码&程序流程梳理

特判a == 0，如果查询vx0要先输出0，等于b再输出1，否则输出-1（注意一下如果x0b，答案要首先输出0）
预处理前1e6的答案，存在pair里面之后排序，去重
计算\(a^{1e6}\)的逆元，还有我们复原需要减去的那一坨东西
然后从第一层开始找，二分查询位置，如果没找到就找下一层，如果发现现在找的位置大于等于n的话要及时结束查找。

#include <bits/stdc++.h>

using namespace std;

typedef long long ll;

const int maxn = 1000000;

int T;

ll x0,n,a,b,p;

ll ksm(ll a,ll b){

    ll res = 1;

    for(;b;b>>=1){

        if(b & 1)res = res*a%p;

        a = a * a % p;

    }

    return res;

}

pair<int,int> node[maxn];

int pos[maxn],val[maxn];

int main(){

    scanf("%d",&T);

    while(T--){

        scanf("%lld%lld%lld%lld%lld",&n,&x0,&a,&b,&p);

        int Q;scanf("%d",&Q);

        if(a == 0){

            while(Q--){

                int v;scanf("%d",&v);

                if(v == x0)

                    puts("0");

                else if(v == b) puts("1");

                else puts("-1");

            }

            continue;

        }

        ll now = x0;

        int up = min(n,(ll)maxn);

        for(int i=0;i<up;i++){

            node[i] = {now,i};

            now = (now * a + b) % p;

        }

        sort(node,node+up);

        int  m = 0;

        for(int i=0;i<up;i++){

            val[m] = node[i].first;

            pos[m++] = node[i].second;

            while(i < up - 1 && node[i].first == node[i+1].first)i++;

        }

        int inv_a = ksm(a,p-2);

        int inv_b = (p-b)%p*inv_a%p;

        ll bb = 0, aa = 1;

        for(int i=0;i<maxn;i++){

            aa = aa * inv_a % p;

            bb = (bb * inv_a + inv_b) % p;

        }

        int r = p / maxn + 1;

        while(Q--){

            int v;scanf("%d",&v);

            int id = lower_bound(val,val+m,v) - val;

            if(id < m && val[id] == v){

                printf("%d\n",pos[id]);continue;

            }

            if(n < maxn){

                puts("-1");continue;

            }

            bool flag = false;

            for(int i=1;i<=r;i++){

                v = (aa * v + bb) % p;

                int id = lower_bound(val,val+m,v) - val;

                if(id < m && val[id] == v){

                    int res = pos[id] + i * maxn;

                    if(res >= n)puts("-1");

                    else printf("%d\n",res);

                    flag = true;break;

                }

            }

            if(!flag)puts("-1");

        }

    }

    return 0;

}

最后提一下，复原的时候也可以先减后乘逆元

那么循环里面bb的更新就变成

ll bb = 0, aa = 1;

for(int i=0;i<maxn;i++){

   aa = aa * inv_a % p;

   bb = (bb*a%p + b) % p;

}

//循环查找中v的更新

v = (v-bb+p)%p*aa%p;

巴特西

2019牛客暑期多校训练营（第五场）C - generator 2 (BSGS)

最新文章

热门文章