EgorGandziy's blog

Привет, Codeforces
By EgorGandziy, history, 7 months ago, In Russian

Можете помочь мне пожалуйста, например, дать идею, как это можно сделать. Есть натуральные числа L и R, нужно найти количество таких чисел a,b,c(l<=a,b,c<=r) на этом отрезке, что a+b=c, причем сделать это нужно меньше чем за линейку, ведь ограничение 0,2сек при 1<=l<=r<=1е9! Можете пожалуйста дать идею или решение возможно, на с++. заранее спасибо

  • Vote: I like it
  • +4
  • Vote: I do not like it

»
7 months ago, # |
  Vote: I like it 0 Vote: I do not like it

Let's fix number a. If it is l, then b is greater or equal l and less or equal r-l. So there is r-l-l+1 numbers that satisfy. If a=l+1, then b is >=l and <=r-l-1. So there r-l-l ways. And so on. You get sum of numbers like (r-l-l+1)+(r-l-l)+(r-l-l-1)+...+1 and it is simple formula.

→ Reply