Noip 2013回転ゲーム


回転ゲーム(circle.cpp/c/pas)【問題説明】n人の仲間(番号0からn-1)が1回転座ってゲームをします.n個の位置番号を時計回りに0からn-1まで与えます.最初は、0番が0番、1番が1番、……というように.ゲームのルールは以下の通りです.各ラウンドの0番目の位置の仲間は時計回りにm番目の位置に、1番目の位置の仲間はm+1番目の位置に、…、このように、n−m番目の位置の仲間は0番目の位置に、n−m+1番目の位置の仲間は1番目の位置に、…、n-1番の位置の仲間は時計回りにm-1番の位置に行きます.今、全部で10 kラウンドが行われていますが、x番の仲間は最後に何番目の位置に着きましたか.【入力】入力ファイル名circle.in. 合計1行を入力し、4つの整数n、m、k、xを含み、2つの整数の間に1つのスペースで区切られます.
【出力】出力ファイル名circle.out. 出力は1行で、10 kホイール後のx番のパートナーがいる位置番号を表す整数が1つ含まれています.
【入出力サンプル】circle.in 10 3 4 5 circle.out 5【データ説明】30%のデータに対して、0<<<7;データの80%に対して、0<107;100%のデータに対して、1<<100000,0<<<<<<<,1≦x≦n,0<<<109.
#include
#include
using namespace std;

int main(){
    freopen("circle.in","r",stdin);
    freopen("circle.out","w",stdout);
    int n,m,k,x;
    scanf("%d%d%d%d",&n,&m,&k,&x);
    int e=10;
    int mod=n;
    int ans=1;
    while(k>0){
        e%=mod;
        if(k%2==1) ans=(e*(ans))%mod;
        k/=2; 
        e=(e*e)%mod; 
    }
    printf("%d",((m*ans)%mod+x)%mod);
    return 0;         
}