526互联

CF1891D Suspicious logarithms

发布时间 2023-12-20 19:36:13作者: FOX_konata

Problem - D - Codeforces

Suspicious logarithms - 洛谷

  • 结论：设 \(l=2^k,r=2^{k+1}-1\)，则 \(g(r)-g(l)\leq 1\)。因为 \(g(l) \geq 2\)，而 \(r<2l\)，因此区间 \([l,r]\) 内最多有一个 \(y^k\)。

  • 因此先枚举 \(i=\log_2 x\)，可以得到底数不变的一个范围 \([L,R]\)，记 \(logL=\log_i L,p=i^{logL+1}\)，判断 \(p\) 是否在区间内即可。

  • 复杂度 \(O(Q \log^2 V)\)，预处理快速幂可以做到 \(O(Q \log V)\)。