読者です 読者をやめる 読者になる 読者になる

Tamflexの貯蔵庫

やる気のない備忘録

codeIQ 2683

F(n) = [n*log10(n)] ([x]はxより大きい最小の整数)
と定義されるとき
G(m) = n (F(n) = m)
となるようなnを求めよ, という問題.
2≦m≦1e10なので大体nの範囲は1~1e9程度, なので多めに見積もって1~1e10の範囲を二分探索すれば一瞬で求まる.

void solve(ll m)
{
  ll l = 1, r = 1e10, t,tmp;
  while(l+1 < r)
  {
    t = (l+r)/2;
    tmp = ceil(t*log10(t));
    if(tmp==m)
    {
      printf("%lld\n",t);
      return;
    }
    else if(tmp > m) r = t;
    else l = t;
  }
  printf("-1\n");
}

int main()
{
  ll m; scanf("%lld",&m);
  solve(m);
}