思い付いた問題

大きな自然数 n が与えられた時、これが aのb乗(a, b 共に自然数)と表される場合は a, b を全部表示するプログラムをかけ。
たとえば n=81 の時、

自分の解答はまだ用意してません。
(log n)**2 程度のアルゴリズムを思いついたんで、n=10の10乗のとき一分以上かかるプログラムは失格とします。

俺コード
後半の a**b≦n を満たす最大のaを計算する二分法の部分は、AD変換でも使われている。AD変換回路は、アナログな入力と、任意のデジタルな比較データとの大小を返すハードしかない。比較を繰り返して数値化する。

#include <stdio.h>
#include <stdlib.h>
typedef unsigned long long u64;

// returns a**b
u64 ipow(u64 a, u64 b)
{
  u64 mbit;
  u64 result = 1;
  u64 apow2 = a;

  for(mbit=1; mbit <= b; mbit <<=1)
  {
    if (b & mbit) result *= apow2;
    apow2 = apow2*apow2;
  }
  return result;
}

int  main(int argc, char **argv)
{
  u64 n = atoll(argv[1]);
  u64 b;

  for (b=2;;b++)
  {
    u64 a=1;
    u64 maxbit_b = 1;

    // estimate number of bits of n**(1/b)
    while(maxbit_b <= (n>>b))
    {
      maxbit_b <<= b; 
      a <<= 1;
    }

    if (a == 1) break;

    if (ipow(a, b) == n)
    {
      printf("a=%lld b=%lld\n", a, b);
      continue;
    }

    u64 cbit;

    // binary search for maximum a such that a**b <= n
    for (cbit = a>>1; cbit != 0; cbit >>=1)
    {
      u64 anext = a | cbit;
      u64 n0 = ipow(anext, b);
      if (n0 == n)
      {
        printf("a=%lld b=%lld\n", anext, b);
        break;
      }
      if (n0 < n) a = anext; 
    }
  }// b loop

  return 0;
}

追記

作ってみましたが、

time a.out 10000000000000000
a=100000000 b=2
a=10000 b=4
a=100 b=8
a=10 b=16
0.000u 0.004s 0:00.00 0.0%      0+0k 0+0io 0pf+0w

10の16乗でも速すぎて時間計測不能