P1965 [NOIP 2013 提高组] 转圈游戏——题解

解题思路

每轮位置增加 $m$，进行 $10^k$ 轮后总位移为 $m\times10^k$。只关心模 $n$ 的结果，因此用快速幂求 $10^k\bmod n$，答案是 $(x+m(10^k\bmod n))\bmod n$。

正确性说明

一轮后位置增加 $m$（模 $n$）。根据加法累积，$R$ 轮后位置为 $x+mR\pmod n$。令 $R=10^k$ 并用模乘替换，得到程序公式。

复杂度分析

时间复杂度 $O(\log k)$，空间复杂度 $O(1)$。

C++17 参考代码

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

#include <bits/stdc++.h> using namespace std; long long qpow(long long a,long long b,long long mod){long long r=1%mod;while(b){if(b&1)r=ra%mod;a=aa%mod;b>>=1;}return r;} int main(){long long n,m,k,x;cin>>n>>m>>k>>x;cout<<(x+m*qpow(10,k,n))%n<<'\n';return 0;}