3285 转圈游戏 2013年NOIP全国联赛提高组

3285 转圈游戏

2013年NOIP全国联赛提高组

时间限制: 1 s

空间限制: 128000 KB

题目等级 : 钻石 Diamond

题目描述 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。

分类标签 Tags 点此展开

这里面有一个公式,需要自己手动推一下

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cmath>
 4 using namespace std;
 5 int n,m,k,x;
 6 int fastpow(int a,int b)
 7 {
 8     int r=1;
 9     int base=a;
10     while(b!=0)
11     {
12         if(b%2==1)
13         r=(r*(base%n))%n;
14         base=(base*base)%n;
15         b=b/2;
16     }
17     return r;
18 }
19 int main()
20 {
21     
22     scanf("%d%d%d%d",&n,&m,&k,&x);
23         printf("%d",((x+fastpow(10,k)*m)%n));
24     return 0;
25 }

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏WD学习记录

Python数据结构与算法笔记(4)

当数据项存储在诸如列表的集合中时,我们说它们具有线性或顺序关系。每个数据项都存储在相对与其他数据项的位置。在Python列表中,这些相对位置是单个项的索引值。由...

1231
来自专栏Python小屋

Python编程一定要注意的那些“坑”(九):0与False

问题描述:在编程时,经常需要单独编写一个函数用来判断某个事件是否成立,如果成立就返回正常结果,否则返回False。在主调函数中根据被调函数的返回值决定下一步的操...

1213
来自专栏程序员互动联盟

【专业技术】STL hash_map使用(一)

今天在使用STL中的hash_map模板遇到使用PTCHAR作为Key时无法对字符串进行正确比较的问题。 hash_map类在头文件hash_map中,和所有其...

3238
来自专栏五分钟学算法

看完动画你还会不懂 快速排序么

由于LeetCode上的算法题很多涉及到一些基础的数据结构,为了更好的理解后续更新的一些复杂题目的动画,推出一个新系列 -----《图解数据结构》,主要使用动画...

1785
来自专栏老司机的简书

老司机出品——包教包会之玩转正则表达式

结束了CoreAnimation系列之后,老司机心里仿佛也轻松了许多。今天说说开发中的一个利器吧,正则表达式。

1693
来自专栏老司机的技术博客

宝宝都能学会的python编程教程16:map和reduce

如果你学习过大数据相关知识一定不会陌生MapReduce。 如果你没有学过大数据,也没关系,本文将带你了解python的map和reduce函数。 map()...

3675
来自专栏CDA数据分析师

除了冒泡排序,你知道Python内建的排序算法吗?

Timsort 是一种对真实数据非常有效的排序算法。Tim Peters 在 2001 年为 Python 编程语言创造了 Timsort。Timsort 首先...

1002
来自专栏程序员宝库

给初学者:JavaScript 的常见注意点

作者: CarterLi 原文:https://segmentfault.com/a/1190000012730162 上篇说了一些 JS 中数组操作的常见误区...

2955
来自专栏数据结构与算法

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2795
来自专栏数据结构与算法

1487 大批整数排序

个人博客:doubleq.win 1487 大批整数排序  时间限制: 3 s  空间限制: 16000 KB  题目等级 : 黄金 Gold 题解 题目描述 ...

2926

扫码关注云+社区

领取腾讯云代金券