题意梗概

n 个小伙伴（编号从 0 到 n-1）围坐一圈玩游戏。按照顺时针方向给 n 个位置编号，从0 到 n-1。最初，第 0 号小伙伴在第 0 号位置，第 1 号小伙伴在第 1 号位置，……，依此类推。游戏规则如下：每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

现在，一共进行了 10^k轮，请问 x 号小伙伴最后走到了第几号位置。

思考

我们假设 x 号小伙伴走了  (10^k*m)步，那么他的位置一定会在 (10^k*m)%n+x的位置  再化简一下

(10^k*m)%n+x = (10^k%n*m%n)%n+x 因为数据范围 m<n 所以最终就是 (10^k%n*m)%n+x

10^k需要快速幂来计算。

#include <cstdio>#include <algorithm>typedef long long ll;ll n,m,k,x;ll quickpow(ll a,ll x){    ll ans = 1;    while(x>0){        if(x & 1) ans = (ans*a)%n;        x>>=1;        a = (a*a)%n;    }    return ans;}int main(){    scanf("%lld%lld%lld%lld",&n,&m,&k,&x);    ll now = quickpow(10,k);    ll Out = (m*now+x)%n;    printf("%lld\n",Out);    return 0;}

[快速幂][NOIP]洛谷1965 转圈游戏