Здравствуйте, infused, Вы писали:

I> Нужно оценить количество делений при нахождении НОД (m,n). Если кто знает формулу подскажите плз...

I>Предпологаю что это порядка log2(max(m,n))... ???
I>Зараннее спасибо.

При желании — можно выйти в O(1), точнее — в ноль

int gcd(int a, int b)
{
  a = abs(a);
  b = abs(b);

  while(a > 1 && b > 1) // можно while(a != 0 && b != 0) -- но это неоптимально
    if(a > b)
      a -= b;
    else
      b -= a;

  if(a == 1 || b == 1)
    return 1;
  else
    return a + b; // одно из них == 0
}