签到题
B generator 1
题意
思路
构造矩阵,十进制矩阵快速幂,在对每位进行二进制快速幂.
代码
C generator 2
题意
给出n,$x_0$,a,b,p求$x_i=(ax_{i-1}+b)$%p,再给出q次查询,每次给出v,求出最小的下标使得$x_i$=v,s输出下标
思路
根据$x_i=ax_{i-1}+b$推导除$x_n=a^nx_0+a^{n-1}b+a^{n-2}b+….+ab+b$再根据等比数列合并得 ‘$ a^n=frac{v*(a-1)+b}{(a-1)x_0+b}$’=v ,下面这部分用逆元求,在用SGBG,形如$a^n$=b(mod p) ,n=i*t-j,t=1e6 ,i=[0,1e3+10],j=[0,1e3+10].在考虑特殊情况a=1,a=0的情况,这道题就解决完成了.