結果

問題 No.1312 Snake Eyes
コンテスト
ユーザー k
提出日時 2020-12-23 19:53:43
言語 C++17
(gcc 13.3.0 + boost 1.87.0)
結果
AC  
実行時間 37 ms / 2,000 ms
コード長 761 bytes
コンパイル時間 1,734 ms
コンパイル使用メモリ 192,548 KB
最終ジャッジ日時 2025-01-17 06:28:50
ジャッジサーバーID
（参考情報） 		judge2 / judge3
このコードへのチャレンジ
（要ログイン）
ファイルパターン 結果
sample AC * 3
other AC * 85
権限があれば一括ダウンロードができます

ソースコード

diff #
raw source code 

#include <bits/stdc++.h>

using namespace std;

#define REP(i,n) for(int i=0; i<(int)(n); i++)

int main() {
  ios_base::sync_with_stdio(0);
  cin.tie(0);

  long long n;
  cin >> n;

  long long ret = n + 1;  // 1 digit

  for (long long x = 1; x * x <= n; x++) {  // 2 digit
    if (n % x) continue;
    long long y = n / x;

    if (x < y - 1) {
      ret = min(ret, y - 1);
    }
    if (y < x - 1) {
      ret = min(ret, x - 1);
    }
  }

  for (long long p = 2; p <= 1000001; p++) {  // multi digit
    double dcur = p + 1;
    long long cur = p + 1;
    while (dcur <= n) {
      if (n % cur == 0 && n / cur < p) {
        ret = min(ret, p);
      }
      dcur = p * dcur + 1;
      cur = p * cur + 1;
    }
  }

  cout << ret << endl;
  
  return 0;
}
0