Question

【急！追分】noip2013 提高组第一题（转圈游戏）c

题目描述 Description
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 号小伙伴最后走到了第几号位置。
输入描述 Input Description
输入共 1 行，包含 4 个整数 n、m、k、x，每两个整数之间用一个空格隔开。
输出描述 Output Description
输出共 1 行，包含 1 个整数，表示 10^k 轮后 x 号小伙伴所在的位置编号。
样例输入 Sample Input
10 3 4 5
样例输出 Sample Output
5
数据范围及提示 Data Size & Hint
对于 30%的数据，0 < k < 7；
对于 80%的数据，0 < k < 10^7；
对于 100%的数据，1 < n < 1,000,000，0 < m < n，1 <= x <=n，0 < k < 10^9。

菜鸟做法..
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
main()
{
int n,m,x,i;
int k;
scanf("%d%d%d%d",&n,&m,&k,&x);
k=pow(10,k);
for(i=1;i<=k;i++)
{
if(x+m<=n-1)
x=x+m;
else
x=x+m-n;
}
printf("%d",x);
system("pause");
}

请问算法有错误吗？我连样例都得不出来 拜托了

Answer 1

/*快速幂模拟题*/
#include <iostream>
#include <cstdio>
using namespace std;
long long n,m,k,x,sum;
long long quite(void){ //快速幂运算
long long a=1,b=10;
while(k!=0){
if(k&1)
a=(a*b)%n;
b=(b*b)%n;
k>>=1;
}
return a;
}
int main(){
long long i;
scanf("%lld%lld%lld%lld",&n,&m,&k,&x);
i=quite();
if(i==1){ //余一的时候就不要加了
printf("%lld",x);
}
else{
sum=(x+m*i)%n; //运行m*10^k次取n的余，10^k次取余用快速幂
printf("%lld",sum);
}
return 0;
}
应该这样可以的，你试试

Answer 2

实际上本例实现的是“模n加”。可以用 取余运算% 实现。

追问

取余这个我有想法 明天进行尝试 请问下模n加是什么。？

追答

比如模5加，则算出来的结果都是在0~4的整数。例如1+1=2, 1+3=4, 1+4=0，1+5=1...实际上就是十进制下计算出的结果对5取余即可

Answer 3

这个可以得出样例的结果啊

追问

输入10 3 4 5？您能得出5？我手边没电脑 明天中午我再试试

Answer 4

我用你的这个跑了一下，没有问题啊，你是编译过不去么？

追问

输入10 3 4 5？您能得出5？我手边没电脑 明天中午我再试试

追答

嗯，你上机试试吧，我这边可以跑得出结果

你上机测试吧，我这边没有问题的