No.8110 WIP Editorial
タグ : / 解いたユーザー数 6
作問者 :
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
WIPFor 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 520240401: 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もしくは右上の雲マークをクリックしてアカウントを作成してください。