转圈游戏

一本通·提高篇 · 代码 · cpp · 难度 4/5 · 共 584 字

n人环坐，每轮顺时针移动m位，求10^k轮后

一本通
练习

正文

/*
原题：转圈游戏
题意：n 人环坐，每轮顺时针移动 m 位，求 10^k 轮后 x 号的位置。
思路：每轮整体平移 m，10^k 轮后位移为 m*10^k，答案 = (x + m*(10^k mod n)) mod n，用快速幂。
复杂度：O(log k) 时间 / O(1) 空间
易错点：先对 n 取模再乘 m 防溢出；10^k 用快速幂避免大数。
*/
#include <bits/stdc++.h>
using namespace std;
long long qpow(long long a,long long b,long long mod){
    long long res=1%mod;
    a%=mod;
    while(b){
        if(b&1){ res=res*a%mod; }
        a=a*a%mod;
        b>>=1;
    }
    return res;
}
int main(){
    long long n,m,k,x;
    cin>>n>>m>>k>>x;
    long long step=qpow(10,k,n);
    long long ans=(x+m*step)%n;
    cout<<ans<<'\n';
    return 0;
}

转圈游戏

正文

一本通·提高篇的其它内容