Rating changes for last rounds are temporarily rolled back. They will be returned soon. ×

Misa-Misa's blog

By Misa-Misa, history, 7 months ago, In English


Most of the number theory problems involving divisors etc that have intended solutions using mobious or inclusion exclusions (I-E), do not really need these buzzwords, there is almost always an easier solution using dp. We can still say its I-E, but code is sort.


Let's calculate dp[i] where dp[i] denotes no of segments which have gcd(min, max) = i. To calculate dp[i], we can first calculate the no of segments which have gcd as multiple i, this part is easy and the same as editorial.


Then subtract dp[k*i] from dp[i] where 2<=k<=n/i. These will remove all segments which have gcd multiple of i but no exactly i. At last just print dp[1].


I forgot to mention one should find these dp values in descending order.

I just don't seem to get it can someone explain it simply and in detail.

These comments were taken from
aryanc403 's twitter.

Problem in discussion is: AtCoder ABC304 F Shift table

  • Vote: I like it
  • +3
  • Vote: I do not like it

7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's consider this problem "for each $$$k$$$ in $$$[1, n]$$$, count the pairs $$$(i, j)$$$ ($$$1 \leq i, j \leq n$$$) such that $$$g := \gcd(i, j) = k$$$".

  • Step 1: for each $$$k$$$, let $$$c_k$$$ be the number of pairs such that $$$g$$$ is a multiple of $$$k$$$. This is easy to calculate: both $$$i, j$$$ must be multiples of $$$k$$$.

  • Step 2: let $$$d_k$$$ be the number of pairs such that $$$g$$$ is exactly $$$k$$$. So $$$g$$$ is a multiple of $$$k$$$, but it can't be $$$2k, 3k, \dots$$$. We can calculate the $$$d_k$$$ in decreasing order. $$$d_k = c_k - \sum_{j \geq 2} d_{jk}$$$.