【13NOIP提高组】转圈游戏（信息学奥赛一本通 1875）（洛谷 1965）

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int n;
 4 int m,k,x;
 5 int read()
 6 {
 7     int f=1;char ch;
 8     while((ch=getchar())<‘0‘||ch>‘9‘)
 9         if(ch==‘-‘)f=-1;
10     int res=ch-‘0‘;
11     while((ch=getchar())>=‘0‘&&ch<=‘9‘)
12         res=res*10+ch-‘0‘;
13     return res*f;
14 }
15 void write(int x)
16 {
17     if(x<0)
18     {
19         putchar(‘-‘);
20         x=-x;
21     }
22     if(x>9)write(x/10);
23     putchar(x%10+‘0‘);
24 }
25 long long ff(int x,int k)
26 {
27     long long res=1;
28     while(k)
29     {
30         if(k%2==1)res=res*x%n;
31         x=x*x%n;
32         k=k/2;
33     }
34     return res;
35 }
36 
37 int main()
38 {
39     n=read();m=read(); 
40     k=read();x=read();
41     long long xx=ff(10,k);
42     xx=xx*m%n;
43     xx=(xx+x)%n;
44     printf("%lld",xx);
45     return 0;
46 }