noip2013——提高组——转圈游戏

#include<iostream>
#include<cstdio>
#include<cstring>
using namespace std;
inline int read(){
    int t=1,num=0;
    char c=getchar();
    while(c>‘9‘||c<‘0‘){if(c==‘-‘)t=-1;c=getchar();}
    while(c>=‘0‘&&c<=‘9‘){num=num*10+c-‘0‘;c=getchar();}
    return num*t;
}
int n,m,k,x,mod,c,ans;
int kuai(int num,int f,int mo){
    int a=1;
    while(f){
        if(f%2)a=((long long)a*num)%mo;
        num=((long long)num*num)%mo;
        f/=2;
    }
    return a;
}
int main()
{
    n=read();m=read();k=read();x=read();
    for(long long i=1;i<=n;i++)
        if(((m*i)%n)==0){mod=i;break;}
    c=kuai(10,k,mod);
    ans=((long long)m*c)%n;
    ans=(ans+x)%n;
    cout<<ans;
    return 0;
}