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

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

大步小步(BSGS)学习：https://oi-wiki.org/math/bsgs/
刘汝佳白书数论中也有入门讲解
如果直接看递推式找不到关系可以先列出前几项
(x_0 = x_0quad x_1=ax_0+bquad x_2=a^2x_0+ab+bquad x_3=a^3x_0+a^2b+ab+b)
(x_4=a^4x_0+sum_{i=0}^3a^ibquad x_5=a^5x_0+sum_{i=0}^4a^ibquad x_6=a^6x_0+sum_{i=0}^5a^ibquad x_7=a^7x_0+sum_{i=0}^6a^ib)
(cdots)
在BSGS中，(a^xequiv bpmod p)的求解是前求出前(m)项((m)通常取(sqrt p))的答案（即(a^i\%p,iin[0,m]))，存在一个数组中便于查询（值和位置一般都要存）,然后再从([m+1,2m])中找答案，如果这一层中有答案那么也就是说(a^{i+m} equiv bpmod p,i+min [m+1,2m]))可以发现如果把指数上的(m)挪到右边，也就是相当于右侧乘了一个(a^m)的逆元，式子变成了(a^iequiv bcdot 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 ightarrow 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 ightarrow 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
",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
",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

相关推荐