Someone please help me understand this.

Правка en4, от Misa-Misa, 2023-10-07 12:11:49

1/4

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.

2/4

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.

3/4

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].

4/4

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

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en5 Английский Misa-Misa 2023-10-07 12:12:11 0 (published)
en4 Английский Misa-Misa 2023-10-07 12:11:49 7
en3 Английский Misa-Misa 2023-10-07 12:11:22 81
en2 Английский Misa-Misa 2023-10-07 12:10:27 112
en1 Английский Misa-Misa 2023-10-07 12:09:14 942 Initial revision (saved to drafts)