题目

504. 转圈游戏

算法标签: 数论, 模运算

思路

看题意不难看出, 计算的是$(x+10^k\times m)\mathrm{mod}n$, 如果直接计算一定会超时, 因此可以使用快速幂进行优化

代码

#include <iostream>
#include <algorithm>
#include <cstring>

using namespace std;

typedef long long LL;

int n, m, k, x;

int quick_pow(int a, int k, int mod) {
    int ans = 1 % mod;
    while (k) {
        if (k & 1) ans = (LL) ans * a % mod;
        a = (LL) a * a % mod;
        k >>= 1;
    }
    return ans;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(0), cout.tie(0);


    cin >> n >> m >> k >> x;
    int ans = x + (LL) quick_pow(10, k, n) * m % n;
    cout << ans % n << "\n";

    return 0;
}