Luogu P1965 转圈游戏

Luogu P1965 转圈游戏

考场上遇到这种题，一定要画图推一下。
不难得到$ans=(x+m imes 10^k)mod n$.
还有就是用同余定理时一定要仔细思考一下，然后该打快速幂就打。

#include<bits/stdc++.h>

using namespace std;

int n,m,k,x;
long long ans;

long long quickPower(int b,int p,int k) {
	long long ans=1;
	if(!p) {
		ans=1%k;
		return ans;
	}
	while(p) {
		if(p%2) {
			ans=(ans*b)%k;
		}
		b=(b*b)%k;
		p/=2;
	}
	return ans;
}

int main()
{
	scanf("%d%d%d%d",&n,&m,&k,&x);
	ans=(x%n+m*quickPower(10,k,n))%n;
	printf("%lld",ans);
	return 0;
}