洛谷 P1965 转圈游戏

思路

每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置，第 1 号位置小伙伴走到第 m+1 号位置，……，依此类推，第n − m号位置上的小伙伴走到第 0 号位置，第n-m+1 号位置上的小伙伴走到第 1 号位置，……，第 n-1 号位置上的小伙伴顺时针走到第m-1 号位置。

因为是个圈，转到\(n\)就变成\(1\)，所以可以进行取模运算（即模\(n\)），\((x+10^k*m)\% n\)就是\(x\)移动\(10^k\)次之后所在的位置，但是求\(10^k\)需要用快速幂，这样就完成了

代码

#include<iostream>

#include<cstdio>

#include<cmath>

#include<cstring>

#include<algorithm>

#include<string>

#include<queue>

#include<stack>

#include<cstdlib>

#define N 1000111

#define MOD 100000007

#define INF 0x3f3f3f3f

#define ll long long

#define int long long

using namespace std;

inline int read() {

	char c=getchar();

	int x=0,f=1;

	for(; !isdigit(c); c=getchar())if(c=='-')f=-1;

	for(; isdigit(c); c=getchar())x=x*10+c-48;

	return x*f;

}

int n,m,k,x;

int ans;

int power(int a,int b){

	int res=1;

	while(b){

		if(b&1)res=res*a%n;

		a=a*a%n;

		b>>=1;

	}

	return res;

}

signed main() {

	//freopen("circle.in","r",stdin);

	//freopen("circle.out","w",stdout);

	n=read(),m=read(),k=read(),x=read();

	int res=power(10,k);

	ans=(x%n+res*m)%n;

	cout<<ans<<'\n';

	fclose(stdin);

	fclose(stdout);

	return 0;

}