Ничего такого не написал, вот и заминусовали

4) Шутки про JKeeJ1e30

Просто если каждый из 2000+ зарегистрировавшихся участников напишет один коммент "Good Luck & Have Fun", то ленту будет невозможно читать. На TopCoder'е пишут такие сообщение, потому что каждое из них содержится в своей комнате.

О_о спасибо, просветил)

всёравно падает(

def d_down( r,l,k ):
  d = (r-l)/(k-1)                                    ### 1 below
  while d > 1:                                       ### 4 below
    if (1+(r/d)-((l+d-1)/d))>=k: return d            ### 2 below
    N = 1 + (r/d)                                    ### 3.2 below
    d -= ( ((N*d)-r) + (N-1) ) / N                   ### 3.4 below
  return 1

"""
basically` 
1) (r-l)/(k-1) is the maximum possible d, given r, l and k
2) the if...return tests if k d's fit between l and r
3) if not, then d must decrease; can't loop decrement (d-=1) with 1E12 ranges, so
3.1) R = d * (1 + r/d) is a multiple of d greater than r, and
3.2) N = (1 + r/d) is the multiplier of d that gets to that R = N*d, so
3.3) (N*d - r) is how far R has to drop to be <= r, so
3.4) ((N*d-r) + (N-1)) / N is the minimum decrease in d which will drop R to <= r
4) go back to 2) above, with decreased, new d

e.g. input m,101,200,2  (answer is 66: *2=132; *3=198)

Initial d = 200 - 101 = 99
but only one multiple of 99 between 101 and 200 inclusive, i.e. 198

       101                       200                    ## boundaries r and l
     99                       198              297      ## multiples of max possible d; R=297; N=3

and if you start decreasing d from 99, then

  98                      196              294           ## multiples of d-1
97                    194               291              ## multiples of d-2
...

so, as d decrements, the numbers on the right (3*d) move faster (3x decrease in d) to get inside 200 than the numbers in the middle (2*d) move to go past 101 (2x decrease in d). the number on the right reaches (or passes) r when 3*d <= 200 i.e. the decrease in d will be the formula in 3.4 above i.e. ( (3*99 — 200) + (3-1) ) / 3 = 33.

the only question is whether 2*d has by that time dropped below l (101), but if it has then repeat the loop.

Дождитесь разбора: сегодня-завтра он появится.

На "подумать": асимптотика авторского решения —

Можна приблизительно оценить g = gcd(i1,i2,..,ik). Если g < 1000000 ,то перебрать его. Если g > 1000000, то оно в виде r/i (целая часть).

Я делал так — будем постепенно уменьшать это число (пусть x). Изначально оцениваем, что оно не более r / k. b = (l — 1) / x. Теперь оцениваем x как не более r / (k + b). Снова b = (l — 1) / x и так, пока не сойдется. Не уверен, что это проходит, но у меня решение упадет независимо от

^^^ Это решение проходит за 140 мс

Это уже совсем манчкинство) Но тут тогда надо внимательно действовать — люди, почему-то, по большей части писать бинпоиск не умеют, у них очень часто вылезают какие-то +-единички, крайние случаи и т.д. и т.п., можно случайно нарваться на это. Не хотел тратить время, думал, может оно еще пригодиться в E, но ничего лучше хэви-лайта не пришло в голову.

Ответ имеет вид [r/z], где z — какое-то целое число. Либо z<=2e6, либо [r/z]<=2e6. Перебрали, выбрали наибольшее.

Нет. 33025443.

Это boolen значение, мне надо f(l, r, k) -  > x т.е. функцию в целые числа.

Same method but WAed!

Maybe you CAN figure it out on paper but it's so much faster this way... so you have to take the easy way to stay ahead of competition.

Indeed, I forgot to write +MOD thing and lock my problem like a fool... 900 points lost will be a real tragedy.

Такой способ мне известен. Но вы сами только что объяснили, почему он не подходит ^_^

I just remembered the case k=1. I hope it doesn't get time out

But I meant problem E div2