思路与算法

每轮位置增加m，10^k轮只需用二进制快速幂求模n的位移；源范围允许x=n也统一求余。

按上述模型建立状态或枚举对象，依代码中的顺序处理输入并输出完整答案。

正确性说明

每次整体平移m，执行r轮平移rm；模n求同余位置可在乘法各步求余。二进制幂将10^k分解为平方乘积，保持结果与已处理位同余。

复杂度

O(log k)时间、O(1)额外空间，初始化均常数。

易错点

k最大接近10^9，不能循环10^k次或构造该大整数；源范围x=n仍需要正规化。

参考代码（C++11）

#include <bits/stdc++.h>
using namespace std;
int main() {
    long long n, m, k, x;
    cin >> n >> m >> k >> x;
    long long a = 10 % n, v = 1;
    while (k) {
        if (k & 1)
            v = v * a % n;
        a = a * a % n;
        k >>= 1;
    }
    cout << (x + m * v) % n << "\n";
}