[AT_ABC106_C]题解(C++)

Part I Preface

• 原题目\(\text{(Luogu)}\)
• 原题目\(\text{(AtCoder)}\)

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;
}