# | User | Rating |
---|---|---|

1 | tourist | 3687 |

2 | ecnerwala | 3600 |

3 | Benq | 3503 |

4 | ksun48 | 3421 |

5 | Um_nik | 3412 |

6 | Radewoosh | 3382 |

7 | maroonrk | 3323 |

8 | Itst | 3239 |

9 | apiadu | 3238 |

10 | ko_osaga | 3232 |

# | User | Contrib. |
---|---|---|

1 | Errichto | 205 |

2 | SecondThread | 197 |

3 | Monogon | 195 |

4 | vovuh | 189 |

5 | Um_nik | 185 |

5 | pikmike | 185 |

7 | antontrygubO_o | 184 |

8 | Ashishgup | 182 |

9 | pashka | 169 |

10 | Radewoosh | 167 |

↑

↓

Codeforces (c) Copyright 2010-2020 Mike Mirzayanov

The only programming contests Web 2.0 platform

Server time: Nov/27/2020 09:17:59 (f3).

Desktop version, switch to mobile version.

Supported by

User lists

Name |
---|

for any $$$ N <= 100000 $$$, maximum

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

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)