結果
問題 | No.757 チャンパーノウン定数 (2) |
ユーザー |
![]() |
提出日時 | 2018-12-09 02:02:23 |
言語 | C++14 (gcc 13.3.0 + boost 1.87.0) |
結果 |
AC
|
実行時間 | 28 ms / 2,000 ms |
コード長 | 989 bytes |
コンパイル時間 | 205 ms |
コンパイル使用メモリ | 33,024 KB |
実行使用メモリ | 5,376 KB |
最終ジャッジ日時 | 2024-09-15 07:32:15 |
合計ジャッジ時間 | 2,873 ms |
ジャッジサーバーID (参考情報) |
judge4 / judge5 |
(要ログイン)
ファイルパターン | 結果 |
---|---|
sample | AC * 3 |
other | AC * 51 |
ソースコード
#include <stdio.h>const int len = 100100;int B,D[len],F[len]; char S[len];bool chk(int l){l--;for (int i=0;i<len;i++) F[i] = D[i];for (int i=0;i<l;i++) F[i] -= (B-1) * (i+1);for (int i=0;i<len;i++) if (F[i] < 0){if (i == len-1) return false;int g = (-F[i] + B-1) / B;F[i] += g * B;F[i+1] -= g;}return true;}int main(){scanf ("%d %s",&B,S);{int l = 0;while (S[l]) l++;for (int j=0;j<l;j++) D[l-j-1] = S[j] - '0';D[0]--;for (int j=0;;j++){if (D[j] >= 0) break;D[j] += B;D[j+1]--;}}int l = 1, r = len;while (l + 1 < r){int m = (l + r) / 2;if (chk(m)) l = m;else r = m;}chk(l);int p = 0;for (int i=len-1;i>=0;i--){p = (p * B + F[i]) % l;}F[0] -= p;for (int i=0;;i++){if (F[i] >= 0) break;while (F[i] < 0){F[i] += B;F[i+1]--;}}for (int i=len-1;i>=0;i--) if (F[i]){if (i) F[i-1] += F[i] % l * B;F[i] /= l;}l--;F[l]++;printf ("%d\n",F[l-p]);return 0;}