n个小伙伴（编号从 0 到 n-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号小伙伴最后走到了第几号位置。
输入格式
输入共1行，包含4个整数n、m、k、x，每两个整数之间用一个空格隔开。
输出格式
输出共1行，包含一个整数，表示10^k轮后x号小伙伴所在的位置编号。
例如：
输入：10 3 4 5
输出：5
没有思路~~~

10个小伙伴围成一圈~每次顺着编号找3步~走了(10^4)%10次~也就是0次~5号小伙伴在5号位置上~

感觉数学公式可以一步到位~

问难点是大数求余~题目要提高难度很可能让10的k超限~小伙伴们跑路还长过马拉松~活活累死了~我汗~

[此贴子已经被作者于2017-1-26 10:43编辑过]

非公式的：
#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <math.h>

void _move(int *a, int n, int m)
{
    int i;
    for (i=0; i<m; i++)
    {
        memmove(a+1, a, n*sizeof(int));
        a[0] = a[n];
    }
}

void _print(int *a, int n)
{
    int i;
    for (i=0; i<n; i++)
        printf("%2d ", a[i]);
    printf("\n");
}

main()
{
    int i, n=10, m=3, k=4,x=5;
    int *a = (int *)malloc((n+1)*sizeof(int));
    for (i=0; i<n; i++)
        a[i] = i;
    printf("n=%d, m=%d, k=%d, x=%d\n", n,m,k,x);
    //_print(a, n);
    for (i=0; i<(int)pow(10,k); i++)
    {
        _move(a, n, m);
        //_print(a, n);
    }
    for (i=0; i<n; i++)
        if (a[i] == x)
            break;
    printf("10^%d轮后%d号小伙伴在%d号位置\n", k,x,i);
    free(a);
}

理论上数学公式可以一步到位~但实际上编程不能一下子得出大数求余的结果~上楼代码可行~~

还可以用"相对论"~人不动标记动~这样只改变标记的位置就不用每执行一次循环就全部变动所有人数编号了~

此题不难，结果为(x + m * 10 ^ k) / n,但是此题出现的问题是幂运算溢出。数学里面有一个快速幂算法
所以，此题的难度不在编程，而在数学算法。
#include "stdio.h"
#include "math.h"
int main()
{
    int n,m,k,x;
    int PowerMod(int, int, int);
    scanf("%d %d %d %d",&n,&m,&k,&x);
    int y = PowerMod(10,k,n);// 10^k mod n
    printf("%d", (x + y) % n);
   
}


int PowerMod(int a, int b, int c)//快速幂算法：a ^ b mod c 网上查的答案
{
    int ans = 1;
    a = a % c;
    while(b>0)
    {
        if(b % 2 == 1)
        ans = (ans * a) % c;
        b = b/2;
        a = (a * a) % c;
    }
    return ans;
}

收到的鲜花

• 九转星河 于 2017-01-26 14:21 送鲜花  10朵   附言：要的就是这种算法~