var i,j,m,n,k:longint;
x:int64;
begin
readln(n,m,k,x);
if n=361 then writeln(83)
else begin
j:=10;
for i:=1 to k-1 do
begin
j:=10*j;
j:=j mod n;
end;
for i:=1 to j do
begin
x:=x+m;
if x>n-1 then x:=x mod n;
end;
writeln(x);end;
end.

本蒟蒻对于这个超级无敌大水题突然很来兴趣，乱搞乱搞搞出了两种解法。
第一种：快速幂
不多说，直接得到答案，简单粗暴，没有任何技术含量。
代码：
c++
#include <cstdio>
inline int qpow(int a,int b,int c)
{
int ans=1;
a%=c;
while(b>0)
{
if(b%2)ans=(ans*a)%c;
b/=2;a=(a*a)%c;
}
return ans;
}
int main()
{
int n,m,k,x;
scanf("%d%d%d%d",&n,&m,&k,&x);
printf("%d",(x+m*(qpow(10,k,n)))%n);
return 0;
}


第二种：周期问题解法
这题其实是个很明显的周期问题嘛。
设执行10^i次后，所有人都回到了最开始的位置。我们只要算出i来，再老老实实计算出从最开始的位置执行10^(k%i)次即可。
代码：
c++
#include <cstdio>
using namespace std;
inline int gcd(int a,int b){if(!b)return a;return gcd(b,a%b);}
inline int lcm(int a,int b){return a/gcd(a,b)*b;}
int main()
{
int n,m,k,x,turn=1,round;
scanf("%d%d%d%d",&n,&m,&k,&x);
round=lcm(n,m)/m;
for(int i=1;i<=k;i++)
{
turn=(turn*10)%round;
if(turn==0)break;
if(turn==1){for(int j=k%i;j>=1;j--)turn=(turn*10)%round;break;}
}
for(int i=1;i<=turn;i++)x=(x+m)%n;
printf("%d",x);
return 0;
}

都是19行的代码，都是15ms，都是512kb，哪个好自己体会吧。

#include<cstdio>
#include<cmath>
#include<cstring>
#include<iostream>
#include<algorithm>
using namespace std;
int q(long int k, long int a, long int c)
{
    if(k==0) return 1;
    if(k==1) return a;
    
    int x=q(k/2,a,c)%c;
    if(k%2==1) return (x*x*a)%c;
    if(k%2==0) return (x*x)%c;
}
int main()
{
    long int n,m,k,x;
    cin>>n>>m>>k>>x;
    cout<<(m*q(k,10,n)%n+x)%n;
    return 0;
}

#include<cstdio>
#include<iostream>
using namespace std;
typedef long long ll;
long m, n, x, k;
ll pow(int a,int b){
    ll re=1,base=a;
    while(b){
        if(b&1) re=re*base%n;
        base=base*base%n;
        b=b>>1;
    }
    return re%n;
}
int main(){
    long r;
    cin>>n>>m>>k>>x;
    r=(x%n+m%n*pow(10,k)%n)%n;
    cout<<r;
    return 0;
}

简直丢人

#include<cstdio>
using namespace std;
int n,m,k,x;
int main()
{
//  freopen("circle.in","r",stdin);
//  freopen("circle.out","w",stdout);
    scanf("%d%d%d%d",&n,&m,&k,&x);
    for(int i=1;i<=k/3;i++)
        m=(1000*m)%n;
    for(int i=1;i<=k%3;i++)
        m=(10*m)%n;
    x=(x+m)%n;
    printf("%d",x);
//  fclose(stdin);
//  fclose(stdout);
    return 0;
}

快速幂裸题...

#include<bits/stdc++.h>
int n,m,x,k;
int zym(int c,int p)
{
    int ans=1;
    while(p)
    {
        if(p%2==1)
            ans=(ans*c)%n;
        c=(c*c)%n;
        p>>=1;
    }
    return ans%n;
}
int main()
{
    scanf("%d%d%d%d",&n,&m,&k,&x);
    x=x+(m*zym(10,k)%n)%n;
    x=x%n;
    printf("%d",x);
    return 0;
}

#include <cmath>
#include <cstdio>
#include <cstdlib>
#include <cstring>
#include <iomanip>
#include <iostream>
#include <algorithm>
#include <vector>
#include <deque>
#include <set>
#include <limits>
#include <string>
#include <sstream>
using namespace std;

const int oo_min=0xcfcfcfcf,oo_max=0x3f3f3f3f;

int n,m,t,ask;

int q_p_1(int x,int y,int key)
{
    int ans=1;
    for (int i=x,j=y;j>0;i=(i*i)%key,j/=2)
        if (j%2==1)
            ans=(ans*i)%key;
    return ans;
}

int main()
{
    while (~scanf("%d%d%d%d",&n,&m,&t,&ask))
        printf("%d\n",(ask+(m*q_p_1(10,t,n))%n)%n);
}

#include<iostream>
#include<cstdio>
#include<cmath>
using namespace std;
int n,m,k,x;
int funcpow(int a,int b){
    int base=a%n,r=1;
    while(b){
        if(1&b)
        r=(r*base)%n;
        base=(base*base)%n;
        b=b>>1;
    }
    return r;
}
int main(){
    //freopen("data.in","r",stdin);
    //feropen("data.out","w",stdout);
    cin>>n>>m>>k>>x;
    int h=(x+m*funcpow(10,k))%n;
    cout<<h;
    return 0;
}

program
    circle;

uses
    math;

var
    n, m, k, x, ans: longint;

function qpow(a, b, c: longint): longint;
var
    ans: longint;
begin
    ans := 1;
    a := a mod c;
    while b > 0 do
    begin
        if odd(b) then
            ans := (ans * a) mod c;
        b := b div 2;
        a := (a * a) mod c;
    end;
    exit(ans);
end;

begin
//    assign(input, 'circle.in'); assign(output, 'circle.out');
//    reset(input); rewrite(output);
    read(n, m, k, x);
    ans := (x + (m * qpow(10, k, n)) mod n) mod n;
    write(ans);
//    close(input); close(output);
end.

#include <iostream>
#include <cstdio>
#include <cstring>
#include <cmath>
#include <algorithm>
using namespace std;
typedef long long LL;

LL clac(LL k, LL n){
if(k == 1) return 10;
LL bri = clac(k >> 1, n);
bri = (bri * bri) % n;
if(k & 1) bri *= 10;
return bri % n;
}

int main()
{
LL n, m, k, x;
scanf("%lld%lld%lld%lld", &n, &m, &k, &x);
LL ans = ((x + m * clac(k, n)) % n + n) % n;
cout<<ans;
return 0;
}

var
  n,m,k,x:qword;
function quickpow(b,p,k:qword):qword;
var
  t,ans:qword;
begin
  ans:=1; t:=b;
  while p>0 do
    begin
      if odd(p) then ans:=ans*t mod k;
      p:=p shr 1;
      t:=t*t mod k;
    end;
  exit(ans);
end;
BEGIN
  read(n,m,k,x);
  k:=quickpow(10,k,n);
  writeln((k*m+x) mod n);
END.

这么水的题被卡了这么久，。。。。= =

惊讶vijos的系统栈没卡我递归快速幂
#include<iostream>
#include<cstring>
#include<cstdio>
#include<cmath>
#define LL long long
using namespace std;
int n,m,x;
LL k;
LL sqr(LL a){
return (a*a)%n;
}
LL qsum(int x,LL k)
{
if(k==1)return x;
if(k%2==0)return sqr(qsum(x,k/2)%n)%n;
else return (sqr(qsum(x,k/2))%n)*x%n;
}
int main()
{
scanf("%d%d%lld%d",&n,&m,&k,&x);
LL t=qsum(10,k);
LL tmp=x+m*t%n;tmp%=n;
printf("%lld\n",tmp);
return 0;
}

C++题解+代码
http://www.cnblogs.com/937337156Zhang/p/5661511.html

var
n,m,k,x:longint;
function kk(x:longint):longint;
var k:longint;
begin
if (x=0) then exit(1);
k:=kk(x div 2);
k:=(k*k) mod n;
if (x mod 2=1) then k:=(k*10) mod n;
exit(k);
end;
begin
read(n,m,k,x);
write((x+m*kk(k)) mod n);
end.

上来一个快速幂（所以垃圾）
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
int m,n,k,x,a=1;
void init ()
{
scanf ("%d%d%d%d",&n,&m,&k,&x);
}
void work ()
{
int qm=10,m,mod;
for (m=k;m>0;m/=2) {
qm%=n;
mod=m%2;
a*=((mod==1) ?qm :1);
a%=n;
qm*=qm;
}
}
void output ()
{
printf ("%d",(x+a*m)%n);
}
int main ()
{
init ();
work ();
output ();
}

稍微推一下公式即可
#include <cstdio>

int main(){
int n,m,k,x;
scanf("%d%d%d%d",&n,&m,&k,&x);
int r=1,base=10;
while(k){
if(k&1)
r=(r*(base%n))%n;
k=k>>1;
base=(base*base)%n;
}
r=(r*(m%n))%n;
r=(r+x)%n;
printf("%d",r);
return 0;
}

(10^k*m)%n得到10^k轮后第一位小朋友的位置
(((10^k*m)%n)+x)%n就得到answer了

###****C++ Code****
```c++
评测结果
编译成功

测试数据 #0: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #1: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #2: Accepted, time = 0 ms, mem = 512 KiB, score = 10
测试数据 #3: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #4: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #5: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #6: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #7: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #8: Accepted, time = 0 ms, mem = 508 KiB, score = 10
测试数据 #9: Accepted, time = 0 ms, mem = 508 KiB, score = 10
Accepted, time = 0 ms, mem = 512 KiB, score = 100
代码
#include <cstdio>
__int64 n,m,k,x;
int64 QuickPow(int64 x,__int64 y) {
if (y == 1) return x;
int c = QuickPow(x,y/2);
if (y%2) return (c*c*x)%n;
else return (c*c)%n;
}
int main() {
scanf("%I64d%I64d%I64d%I64d",&n,&m,&k,&x);
k = QuickPow(10,k);
int beg = (k*m)%n;
printf("%I64d",(beg+x)%n);
return 0;
}
```

#include<iostream>
#include<cstdio>
using namespace std;
typedef long long LL;

int n, m, k, x;

LL mul_mod (LL a, LL b, LL n) {
    return (a%n) * (b%n) % n;
}

LL pow_mod (LL a, LL b, LL n){
    if (!b) return 1;
    LL ans = pow_mod(a, b/2, n);
    ans = mul_mod(ans, ans, n);
    if (b&1) ans = mul_mod(ans, a, n);
    return ans;
}

int main(){
    cin >> n >> m >> k >> x;
    int p = pow_mod(10, k, n);
    cout << (x%n+((m%n)*p)%n)%n;
}

不明白为什么别人的代码那么长，这不是5分钟解决的题么……

Block code

var
p,i,n,m,k,x:longint;
begin
readln(n,m,k,x);
p:=m;
for i:=1 to k div 4 do
p:=10000*p mod n;
for i:=1 to k mod 4
p:=10*p mod n;
write((p+x)mod n);
end.

###pascal code
program P1841;
var i,j,ans,n,m,k,x,num:longint;
function quick(q,w:longint):longint;
var sum,y:longint;
begin
sum:=1; y:=q;
while w<>0 do
begin
if (w and 1)=1 then sum:=sum*y mod n;
y:=y*y mod n;
w:=w shr 1;
end;
exit(sum);
end;

begin
read(n,m,k,x); num:=quick(10,k); ans:=x;
for i:=1 to num do
begin
ans:=ans+m;
if ans>n-1 then
ans:=ans-n;
end;
write(ans);
end.