結果

問題 No.3355 対数の整数部分
コンテスト
ユーザー 👑 p-adic
提出日時 2024-05-30 08:43:51
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 2 ms / 2,000 ms
コード長 778 bytes
コンパイル時間 1,727 ms
コンパイル使用メモリ 194,860 KB
実行使用メモリ 7,848 KB
最終ジャッジ日時 2025-11-14 20:53:25
合計ジャッジ時間 2,580 ms
ジャッジサーバーID
（参考情報） 		judge2 / judge4
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
other AC * 30
権限があれば一括ダウンロードができます

ソースコード

diff # 

#include <bits/stdc++.h>
using namespace std;
int main(){
  long long N , M; cin >> N >> M;
  double logN = log( N ) , logM = log( M );
  int n = logM / logN;
  n = max( 0 , n - 1 );

  // 繰り返し二乗法でNのn乗を計算してN_nに格納。愚直にNをn個掛けても良いがそれより早い。
  int exponent = n;
  long long power = N , N_n = 1;
  while( exponent > 0 ){
    if( exponent % 2 == 1 ){
      N_n *= power;
    }
    power *= power;
    exponent /= 2;
  }

  // Nのn乗とMを比較し、望ましい不等式が成立している限りnに1を加算する。
  while( N_n <= M ){
    M /= N; // N_n *= Nだとオーバーフローする。
    n++;
  }

  // Nのn乗がMを超えたので、nに1を減算する。
  n--;
  cout << n << "\n";
}
0