...And not as difficult as it seems to be. My program on Pascal gets AC within 0.796 sec without complicated optimizations and even without sorting, grouping, ets. Just some good precalc ideas realized properly :)

Dima, I better
901327    21:51:38
21 авг 2005    Anatoliy 'Tolyan_NO' Tolstobroff    1318    Pascal    Accepted
    0.687    281 КБ

Not use binaru searching use O(39), but cleaver.

My solution uses additional array [65536] that helps to calculate int(log2()) of 16-bit numbers faster.
GaLL 1318 C++ Accepted 0.406 314 КБ

Optimized binary searching:
 no extras comparisons, no cycles
 6 comparisons only !!!

int Find( Tm_LargeNumber<> &n )
{
    if (n < Pow[16])
        if (n < Pow[8])
            if (n < Pow[4])
                if (n < Pow[2])
                    if (n < Pow[1])
                        return 0;
                    else
                        return 1;
                else
                    if (n < Pow[3])
                        return 2;
                    else
                        return 3;
            else
                if (n < Pow[6])
                    if (n < Pow[5])
                        return 4;
                    else
                        return 5;
                else
                    if (n < Pow[7])
                        return 6;
                    else
                        return 7;
        else
            if (n < Pow[12])
                if (n < Pow[10])
                    if (n < Pow[9])
                        return 8;
                    else
                        return 9;
                else
                    if (n < Pow[11])
                        return 10;
                    else
                        return 11;
            else
                if (n < Pow[14])
                    if (n < Pow[13])
                        return 12;
                    else
                        return 13;
                else
                    if (n < Pow[15])
                        return 14;
                    else
                        return 15;
    else
        if (n < Pow[32])
            if (n < Pow[24])
                if (n < Pow[20])
                    if (n < Pow[18])
                        if (n < Pow[17])
                            return 16;
                        else
                            return 17;
                    else
                        if (n < Pow[19])
                            return 18;
                        else
                            return 19;
                else
                    if (n < Pow[22])
                        if (n < Pow[21])
                            return 20;
                        else
                            return 21;
                    else
                        if (n < Pow[23])
                            return 22;
                        else
                            return 23;
            else
                if (n < Pow[28])
                    if (n < Pow[26])
                        if (n < Pow[25])
                            return 24;
                        else
                            return 25;
                    else
                        if (n < Pow[27])
                            return 26;
                        else
                            return 27;
                else
                    if (n < Pow[30])
                        if (n < Pow[29])
                            return 28;
                        else
                            return 29;
                    else
                        if (n < Pow[31])
                            return 30;
                        else
                            return 31;
        else
            if (n < Pow[36])
                if (n < Pow[34])
                    if (n < Pow[33])
                        return 32;
                    else
                        return 33;
                else
                    if (n < Pow[35])
                        return 34;
                    else
                        return 35;
            else
                    if (n < Pow[37])
                        return 36;
                else
                   if (n < Pow[38])
                        return 37;
                   else
                        return 38;
}

I think it's much more interesting to find O(n) solution.
It is really beautiful.