問題一覧 > ネタ問題

No.8110 WIP Editorial

レベル : / 実行時間制限 : 1ケース 4.000秒 / メモリ制限 : 512 MB / 標準ジャッジ問題
タグ : (AC するまで非表示) / 解いたユーザー数 6
作問者 : KumaTachiRen / テスター : 👑 p-adic
お気に入りにしたユーザー ProblemId : 10744 / 自分の提出
問題文最終更新日: 2024-03-10 17:16:00
This statement was translated by AI (claude-opus-5-5, effort medium) and may contain errors or differ in nuance from the original. The original statement takes precedence. Back to the original
yukicoder April Fool Contest 2024 (順位表) の他の問題:

Editorial

WIP: discussion of the number of divisors

Therefore, letting $M$ be the maximum value of $x$ given in query 3 and $C$ be the number of primes less than or equal to $M$, it suffices to support range update / range add / range sum for the exponent of each of the $C$ primes, and this can be implemented using a lazy segment tree.

Implementation details WIP

For queries 1 and 2, we factorize $x$ into primes and perform $C$ range updates / range additions, for a time complexity of $O(\log x+C\log N)$.

For query 3, the answer can be computed from the sum of the exponents for each prime factor, for a time complexity of $O(C\log N)$.

Under the constraints of this problem, $C\leq 25$, so implementing the above solves this problem.


Notes

  • Sample ideas
    • 24/4/1: 3/20 24 12/5/3 1 3 3/2 1 2 2/3 1 1 4/1 2 3 49/3 2 2 5
    • 20240401: Can it be constructed by running random trials? → It worked, for example $61\times 137\times 213\times 243\times 577$
  • Slow languages probably won't pass unless $Q\leq 3\times10^4$ or so? Instead, make it $A_i\leq 10^{18}$
  • ↑ With TL 4s, random cases passed on PyPy3, so it's OK. Something like $O(C\sqrt{N})$ also passes, but that can't be helped

提出するには、Twitter 、GitHub、 Googleもしくは右上の雲マークをクリックしてアカウントを作成してください。