拔山蓋世
可以在 O(p) 的时间里求解方程 ax≡b(modp) 的整数解 x。
设 t=⌊q⌋,∀j∈[0,t)∩Z,都令 x=i×t−j,那么就有:
ai×t−j≡b(modp)
同时乘以 aj 得到:
(ai)t≡b×aj(modp)
那么枚举所有的 j,把 b×aj 丢到一个集合里。
然后再枚举 i,查询集合里是否有 (at)i,这样就知道了 i,j 也就知道了 x 了。
CF919E Congruence Equation
因为 ax≡ax+(p−1)(modp),x≡x+p(modp),所以 x×axmodp 的值是以 p×(p−1) 为周期的。
令 x=k(p−1)+r 其中 0≤r<p−1,k,r∈Z+。
那么原式就可以写作:
(r−k)×ar≡b(modp)
移项,得到:
r−k≡b×a−r(modp)
枚举 r,计算 k,得到 x。
CF906D Power Tower
为什么会有一个叫欧拉降幂版的玩意,欧拉就知道 xjb 在哪里乱开发一些东西。
ab={ababmodϕ(p)+ϕ(p)b<ϕ(p)Other wise.
设 f(l,r,p) 表示 wlwl+1⋯wrmodp,如果 wl+1wl+2⋯wrmodp≥ϕ(p),就有 f(l,r,p)=wlf[l+1,r,ϕ(p)]+ϕ(p)modp。
对指数进行递归求解,直到当递归到 p=1 或者 l=r+1 时停止,返回 1。
因为当 p 为偶数时 ϕ(p)≤2p,且当 p 为奇数时 2∣ϕ(p),所以递归的次数不会超过 logp。
CF757E Bash Plays with Functions
设 g(x) 表示 x 互不相同的质因子个数,容易理解 f0(n)=2g(n)。
fr(n)=d∣n∑fr−1(n)
所以 fr 是积性函数,所以:
fr(n)=∏f(aibi)
同时还有:
fr(aibi)=j=0∑bifr−1(aij)
因为 f0(aibi)=2,所以可以递推求解。
因为 f 的值与 ai 无关,所以对于所有的 r 和 bi 全部预处理,因为 bi≤log2(n)。
时间复杂度为 O(rlogn)。
CF1097D Makoto and a Blackboard
对于 n=pα 的情况,设 fi,j 表示有 i 次操作之后变成 pj 的概率。
那么 fi,j=t=j∑αt+1fi−1,t,那么简化一下就是 fi,j=fi,j+1+j+1fi−1,j。
因为每一个质因子相互独立,所以直接乘起来。
HDU 5628 Clarke and math
当 k=1 时:
g(i)=i1∣i∑f(i1)=ab=1∑f(a)×1(b)=(f∗1)(i)
当 k=2 时:
g(i)=i1∣i∑i2∣i1∑f(i2)=i1∣i∑g(i1)=ab=i∑g(a)×1(b)=(f∗12)(i)
所以得到:
g(i)=(f∗1k)(i)
六省联考 2017 相逢是问候
ab={ababmodϕ(p)+ϕ(p)b<ϕ(p)Other wise.
对于一大堆修改操作之后,肯定是 cccai 这种形式的,考虑欧拉降幂。
对于每一次降幂之后,p←φ(p) 所以最多 logp 次。
所以只有前 logp 操作有效,重口味线段树,有势能所以做完了。