Part I Preface
Part II Sketch
- 给定一个字符串 \(s\) 以及一个整数 \(k\)。
- 该字符串为纯数字串。其中的数字 \(x\) 会在 \(k\) 天后变为 \(x^{k - 1}\) 个 \(x\)。
- 求出 \(10^{15}\) 天后，串 \(s\) 的第 \(k\) 位是什么。
- \(|s| < 100, k < 10^{18}\)
Part III Analysis
我们从最小的情况说起。假设当前位为 \(2\)，那么 \(10^{15}\) 天后会变成 \(2^{10^{15} - 1}\) 个 \(2\)。显然，\(2\) 的个数早就超过了 \(k\) 的最大值，那么 \(> k\) 的数就更不用说了。所以我们只需要找到第一个非 \(1\) 的数的位置，输出即可。
Part IV Code
#include <bits/stdc++.h>
using namespace std;
string s;
long long k;
int main(){
cin >> s >> k;
int len = s.size();
for(int i = 0; i < k && i < len; i++){
if(s[i] != '1'){
cout << i << '\n';
return 0;
}
}
cout << "1\n";
return 0;
}