拔山蓋世

可以在 O(p)O(\sqrt{p}) 的时间里求解方程 axb(modp)a^x \equiv b\pmod p 的整数解 xx

t=qt=\lfloor\sqrt{q}\rfloorj[0,t)Z\forall j\in[0,t)\cap\mathbb{Z},都令 x=i×tjx=i\times t-j,那么就有:

ai×tjb(modp)a^{i\times t-j}\equiv b\pmod p

同时乘以 aja^{j} 得到:

(ai)tb×aj(modp)(a^{i})^t\equiv b\times a^j\pmod p

那么枚举所有的 jj,把 b×ajb\times a^j 丢到一个集合里。

然后再枚举 ii,查询集合里是否有 (at)i(a^t)^i,这样就知道了 i,ji,j 也就知道了 xx 了。

CF919E Congruence Equation

因为 axax+(p1)(modp)a^x\equiv a^{x+(p-1)}\pmod pxx+p(modp)x\equiv x+p\pmod p,所以 x×axmodpx\times a^x\bmod p 的值是以 p×(p1)p\times (p-1) 为周期的。

x=k(p1)+rx=k(p-1)+r 其中 0r<p10\le r< p-1k,rZ+k,r\in\mathbb{Z}^+

那么原式就可以写作:

(rk)×arb(modp)(r-k)\times a^r\equiv b\pmod p

移项,得到:

rkb×ar(modp)r-k\equiv b\times a^{-r}\pmod p

枚举 rr,计算 kk,得到 xx

CF906D Power Tower

为什么会有一个叫欧拉降幂版的玩意,欧拉就知道 xjb 在哪里乱开发一些东西。

ab={abb<ϕ(p)abmodϕ(p)+ϕ(p)Other wise.a^b=\left\{\begin{matrix}a^b& b<\phi (p)\\a^{b\bmod \phi(p)+\phi(p)}&\text{Other wise.}\end{matrix}\right.

f(l,r,p)f(l,r,p) 表示 wlwl+1wrmodpw_l^{w_{l+1}^{\cdots^{w_r}}}\bmod p,如果 wl+1wl+2wrmodpϕ(p){w_{l+1}}^{w_{l+2}^{\cdots^{w_r}}}\bmod p\ge \phi(p),就有 f(l,r,p)=wlf[l+1,r,ϕ(p)]+ϕ(p)modpf(l,r,p)={w_l}^{f[l+1,r,\phi(p)]+\phi(p)}\bmod p

对指数进行递归求解,直到当递归到 p=1p=1 或者 l=r+1l=r+1 时停止,返回 11

因为当 pp 为偶数时 ϕ(p)p2\phi(p)\le \dfrac{p}{2},且当 pp 为奇数时 2ϕ(p)2\mid \phi(p),所以递归的次数不会超过 logp\log p

CF757E Bash Plays with Functions

g(x)g(x) 表示 xx 互不相同的质因子个数,容易理解 f0(n)=2g(n)f_0(n)=2^{g(n)}

fr(n)=dnfr1(n)f_{r}(n)=\sum\limits_{d\mid n} f_{r-1}(n)

所以 frf_r 是积性函数,所以:

fr(n)=f(aibi)f_r(n)=\prod f({a_i}^{b_i})

同时还有:

fr(aibi)=j=0bifr1(aij)f_r({a_{i}}^{b_i})=\sum\limits_{j=0}^{b_i} f_{r-1}({a_i}^j)

因为 f0(aibi)=2f_0({a_i}^{b_i})=2,所以可以递推求解。

因为 ff 的值与 aia_i 无关,所以对于所有的 rrbib_i 全部预处理,因为 bilog2(n)b_i\le \log_2(n)

时间复杂度为 O(rlogn)O(r\log n)

CF1097D Makoto and a Blackboard

对于 n=pαn=p^{\alpha} 的情况,设 fi,jf_{i,j} 表示有 ii 次操作之后变成 pjp^j 的概率。

那么 fi,j=t=jαfi1,tt+1f_{i,j}=\sum\limits_{t=j}^{\alpha}\dfrac{f_{i-1,t}}{t+1},那么简化一下就是 fi,j=fi,j+1+fi1,jj+1f_{i,j}=f_{i,j+1}+\dfrac{f_{i-1,j}}{j+1}

因为每一个质因子相互独立,所以直接乘起来。

HDU 5628 Clarke and math

k=1k=1 时:

g(i)=i1if(i1)=ab=1f(a)×1(b)=(f1)(i)g(i)=\sum\limits_{i_1\mid i} f(i_1)=\sum\limits_{ab=1}f(a)\times 1(b)=(f*1)(i)

k=2k=2 时:

g(i)=i1ii2i1f(i2)=i1ig(i1)=ab=ig(a)×1(b)=(f12)(i)g(i)=\sum\limits_{i_1\mid i}\sum_{i_2\mid i_1} f(i_2)=\sum\limits_{i_1\mid i} g(i_1)=\sum\limits_{ab=i} g(a)\times 1(b)=(f*1^2)(i)

所以得到:

g(i)=(f1k)(i)g(i)=(f*1^k)(i)

六省联考 2017 相逢是问候

ab={abb<ϕ(p)abmodϕ(p)+ϕ(p)Other wise.a^b=\left\{\begin{matrix}a^b& b<\phi (p)\\a^{b\bmod \phi(p)+\phi(p)}&\text{Other wise.}\end{matrix}\right.

对于一大堆修改操作之后,肯定是 cccaic^{c^{c^{a_i}}} 这种形式的,考虑欧拉降幂。

对于每一次降幂之后,pφ(p)p\gets \varphi(p) 所以最多 logp\log p 次。

所以只有前 logp\log p 操作有效,重口味线段树,有势能所以做完了。