记录编号	353374	评测结果	AAAAAAAAAAA
题目名称	[NOIP 2013]转圈游戏	最终得分	100
用户昵称	NemoAre	是否通过	通过
代码语言	C++	运行时间	0.002 s
提交时间	2016-11-17 23:17:55	内存使用	0.29 MiB

//
//  Qpw.cpp
//  CAlgo
//
//  Created by Arendelle on 2016/11/17.
//  Copyright © 2016年 AdTech. All rights reserved.
//

#include <cstdio>
typedef long long lovelive;
lovelive qcpw(lovelive a, lovelive b, lovelive m){ //(a^b)%m
    lovelive res = 1;
    a %= m;
    while(b>0){
        if(b%2==1){
            res = (res*a)%m;
        }
        b/=2;
        a = (a*a)%m;
    }
    return res;
}
lovelive gcd(lovelive a,lovelive b){
    return b==0?a:gcd(b, a%b);
}
int main(){
    lovelive n,m,k,x;
    FILE *fp,*fp1;
    fp = fopen("CircleNOIP2013.in", "r");
    fp1 = fopen("CircleNOIP2013.out", "w+");
    fscanf(fp, "%lld %lld %lld %lld",&n,&m,&k,&x);
    lovelive temp = gcd(n, m);
    temp = n / temp; // temp is the total time cost to get back
    lovelive left = qcpw(10, k, temp);
    left = ((left%n) * (m%n)) % n;
    left += x;
    if(left>=n){
        left -= n;
    }
    fprintf(fp1,"%lld", left);
    return 0;
}