Interesting Question on Co-primes
Разница между en1 и en2, 156 символ(ов) изменены
I found this question somewhere online, which went as follows:↵
For each integer x in a given range [L, R], find the count of integers in the given range that are co-prime with x.↵
Constraints: 1 <= L <= R <= 1e5↵

A brute force solution would fail the time limit, dExample: For L = 2, R = 4, the co-prime pairs would be:↵

2 -> (2,3) so count = 1↵
3 -> (3,2), (3,4) so count = 2↵
4 -> (4,3) so count = 1↵

D
oes anyone have an optimal solution for this?

История

 
 
 
 
Правки
 
 
  Rev. Язык Кто Когда Δ Комментарий
en2 Английский darth_chef 2020-08-22 09:25:05 156
en1 Английский darth_chef 2020-08-22 09:17:30 336 Initial revision (published)