记录编号	543961	评测结果	AAAAAAAAAAA
题目名称	[NOIP 2013]转圈游戏	最终得分	100
用户昵称	ShallowDream雨梨	是否通过	通过
代码语言	C++	运行时间	0.005 s
提交时间	2019-10-11 20:31:56	内存使用	13.66 MiB

#include<bits/stdc++.h>
#define ll long long 
using namespace std;
ll gcd(int x,int y){
	return y==0?x:gcd(y,x%y);
}
ll s(ll a,ll b,ll k){
	ll ans=1,base=a;
	while(b>0){
	if(b&1){
	ans*=base;ans%=k;}
	base*=base;
	base%=k;
	b>>=1;}
	return ans%k;}
int main(){
    freopen("CircleNOIP2013.in","r",stdin);
    freopen("CircleNOIP2013.out","w",stdout);
   ll n,m,k,x,mod;
   	cin>>n>>m>>k>>x;
	mod=n/gcd(n,m);
  	// cout<<mod;
   	cout<<(x+m*s(10,k,mod))%n;
    return 0;
}