ぱーぽーの競プロ記

競技プログラミングに関することを書きます。

TopCoder SRM 628 Div1 Easy : DivisorsPower

解法・感想など


本番で解けなかったやつ。

問題文読んだ瞬間、二分探索っぽい!って思ったが、1から順番にn^d(n)を列挙してみると

n = 1: 1
n = 2: 4
n = 3: 9
n = 4: 64
n = 5: 25
n = 6: 1296
n = 7: 49
n = 8: 4096
n = 9: 729
n = 10: 10000
n = 11: 121
n = 12: 2985984
n = 13: 169
n = 14: 38416
n = 15: 50625
n = 16: 1048576
n = 17: 289
n = 18: 34012224
n = 19: 361
n = 20: 64000000
...

となってこれ無理じゃんとなって、結局いろいろやったがダメだった。

なぜここでもっと考えられなかったのか...と思うが、ここで上の値がバラバラなのはd(n)の値が異なるから。

というわけで、d(n)の値を固定して二分探索をすればよい。
制約から見て[2, 63]くらいまでやればよい。

冪乗の計算でオーバーフローするので、計算を工夫する必要がある。私は、

long long getP(long long x, int d) {
  lli res = 1;
    
  for(int i = 0; i < d; i++) {
    if(res > 1e18 / x) return -1;
    res *= x;
  }

  return res;
}

のようにしてオーバーフローを回避した。

(こういう問題をサクッと解けるようになりたい。)


ソースコード

typedef long long int lli;

class DivisorsPower {
public:

  long long getD(long long n) {
    int res = 0;
    
    for(int i = 1; i * i <= n; i++) {
      if(n % i == 0) {
        if(n / i == i) res++;
        else res += 2;
      }
    }

    return res;
  }

  long long getP(long long x, int d) {
    lli res = 1;
    
    for(int i = 0; i < d; i++) {
      if(res > 1e18 / x) return -1;
      res *= x;
    }

    return res;
  }

  long long findArgument(long long n) {
    
    for(int i = 2; i < 64; i++) {
      lli lb = 0;
      lli ub = n;
      
      while(ub - lb > 1) {
        lli mid = (lb + ub) / 2; 
        lli tmp = getP(mid, i);

        if(tmp == -1 || n < tmp) ub = mid;
        else if(n > tmp) lb = mid;
        else {
          if(getD(mid) == i) return mid;
          else break;
        }
      }
    }

    return -1;
  }