### zeus_iitg's blog

By zeus_iitg, history, 4 weeks ago, , # Problem Description

### N <= 100000 Comments (2)
 » 4 weeks ago, # | ← Rev. 2 →   for any $N <= 100000$, maximum distinct prime divisors is 6. Let us iterate over the denominator. For a particular iteration let's say denominator is k. All values in the range $[i * k, (i + 1) * k)$ will contribute a sum of $i$ to the sum. We wish to find how many number in this range are co-prime to k, and if we suppose that number to be $t$, we can simply add $t * i$ to our final answer for this range of values with denominator $k$.To find the number of coprime values in this range we can make use of the fact that number of distinct divisors of all numbers we require is <= 6 and hence can make use of inclusion exclusion principle to find the number. [Comment if more clarity is required on this]Care must be taken for final iteration for each denominator when the range would be $[i * k, min(N, (i + 1) * k))$The complexity for the solution will be $O(2^M * Nlog(N))$ where $O(2^M)$ (M is the maximum number of distinct prime divisors for any number $< N$ (6 in this case)) is contributed by inclusion exclusion logic and $O(Nlog(N))$ is your sieve's complexity.
 » 4 weeks ago, # | ← Rev. 2 →   This problem can be solved by seive. The main idea is as followed.Let $f(g)$ be the summation of pair which their gcd is equal to $g$. Then we can write $f(g)$ as ...$f(g) =$ $\sum_{gcd(i,j) = g} \lfloor{\frac{j}{i}} \rfloor$ $= \sum_{g | x, g | y} \lfloor{\frac{y}{x}}\rfloor - \sum_{d \ge 2} f(g * d)$. You should iterate $g$ from $n$ to $1$ to calculate this with seive. The key idea is to calculate $\sum_{g | x, g | y} \lfloor{\frac{y}{x}}\rfloor$ in $O(1)$ while doing seive. (Not hard)The answer is $f(1)$. Code (If you want)