P1965 转圈游戏

#include<bits/stdc++.h>
using namespace std;
int num[100000000],cnt=1,x,m,n,k;
long long int po(int k)
{
    if(k==0)return 1;
    long long int ans=po(k/2);
    if(k%2==0)return ans*ans%cnt;
    else return ans*ans*10%cnt;     
}
int main()
{
    cin>>n>>m>>k>>x;
    num[0]=x;
    int temp=(x+m)%n;
    num[1]=temp;
    while(1)
    {
        temp=(temp+m)%n;
        if(temp==x)break;
        else num[++cnt]=temp;
    }
    cout<<num[po(k)];
}