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,

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

 » 7 months ago, # |   0 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}$.