AGC003

Posted on Edited on In

AtCoder Grand Contest 003

D - Anticube

  1. 直接将每个数的立方因子去掉,作为代表元素. \(O(A^{\frac13}/\ln A)\)
  2. 每个集合与其互补集合之间只能选择1个.
  3. 如何寻找互补集合?
    • 对于\(p^3 \le 10^{10}\)的因子,暴力处理.
    • 剩下的部分只能是\(p\),\(p^2\)或\(pq\)形式, 查表.

E - Sequential operations on Sequence

  1. 首先\(\{a_n\}\)可以变成单调栈.
  2. 考虑倒着处理问题, 每次把后缀加回前缀, 最后得到的数列就是每个数字的出现次数.
  3. 实现显然 \(O(Q\log Q\log N)\)

F - Fraction of Fractal