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

我不是女神ヾ 2021-10-29 07:48 259阅读 0赞

[题目链接][Link 1]  
题意：

*  给定\\(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/][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的大小。  
代码&程序流程梳理

1.  特判a == 0，如果查询v==x0要先输出0，等于b再输出1，否则输出-1（注意一下如果x0==b，答案要首先输出0）
2.  预处理前1e6的答案，存在pair里面之后排序，去重
3.  计算\\(a^\{1e6\}\\)的逆元，还有我们复原需要减去的那一坨东西
4.  然后从第一层开始找，二分查询位置，如果没找到就找下一层，如果发现现在找的位置大于等于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;

转载于:https://www.cnblogs.com/1625--H/p/11291238.html

[Link 1]: https://ac.nowcoder.com/acm/contest/885/C
[https_oi-wiki.org_math_bsgs]: https://oi-wiki.org/math/bsgs/