noip2017数据3转圈游戏哪里有数据

来源：蜘蛛抓取(WebSpider) 时间：2016-09-16 08:04 标签： noip测试数据
数据结构与算法（39）
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 号位置。
现在，一共进行了 10k&轮，请问 x 号小伙伴最后走到了第几号位置。
输入共 1 行，包含 4 个整数 n、m、k、x，每两个整数之间用一个空格隔开。
输出共 1 行，包含 1 个整数，表示 10^k 轮后 x 号小伙伴所在的位置编号。
<span style="color:#
<span style="color:#
<span style="color:#
<span style="color:#
对于 30%的数据，0 & k & 7；
对于 80%的数据，0 & k & 107；
对于 100%的数据，1 & n & 1,000,000，0 & m & n，1 ≤ x ≤ n，0 & k & 109。
#include&iostream&
#include&cstdio&
#include&cstring&
long long m,n,x,
long long sf(long long k){
&if(k==0)return 1L;
&&if(k%2==1){
&&&tot=sf(k/2)%n;
&&&return (((10*tot)%n)*tot)%n;
&&&tot=sf(k/2)%n;
&&&return tot*
int main(){
&freopen(&circle.in&,&r&,stdin);
&freopen(&circle.out&,&w&,stdout);
&cin&&n&&m&&k&&x;
&tot=sf(k);
&cout&&((x&#43;tot*m)%n);
&return 0;
假作真时真亦假
无为有处有还无
访问：15362次
积分：2928
排名：第14115名
原创：204篇
转载：22篇
评论：35条
文章：37篇
(1)(43)(37)(84)(5)(2)(5)(7)(2)(1)(15)(4)(1)(19)他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)NOIP 提高组 复赛（60）
NOIP2013 提高组 复赛 day1 circle 转圈游戏
1.题目读下来，惊呆了，这可是第一题啊。
2.进行模拟，弄明白了题意。
3.看了数据范围，好吧，本题第一目标30分。
4.开始编程，定了目标后，就比较简单了。
5.样例通过，第一次提交，得分0，原因：new_x=(x&#43;m)%n;//此处new_x=x&#43;m；得分0
6.马上进行修改，第二次提交，得分30，满意了。
30分的目标，此题耗时：10分钟即可。从整个考试来说，还是很划算的。
7.做题的时候感觉本题要用初等数论的取余的一些性质，目前还达不到这个水平。
8.有个疑问，提交时，是否能知道成绩，是否能提交多次，若能，是否要罚分。
9.突然想到，每次*10就取一次余，应该可以得到更多的分。提交，得分80，非常满意。
80分的目标，应该是编完其它程序再回过来做。
耗时：30分钟
10.剩下的20分，坚决不看解答，等能力到了，再回来做。要靠自己做出。
11.将80分代码中int 改成long long，得分90.
12.接下来，分数再也提不上了，搜索网络，发现---快速幂，看来不学新的东西，就无法AC。
13.好吧，坐下来，学学快速幂。
14.http://wenku.baidu.com/link?url=Cyhe-A3PtI8YD9xgNW3ss7kBQzQ3nGtUVZojX_QkRRonq3y7du4k3zsrpg7mfKqcqqM5UhiRqOQfaU-PXwwGtY60uichOq9y_F1HakD54Da文章写得不错，也就是为什么要用快速幂，分析得很透彻。
15.用快速幂编码，提交AC。
16.快速幂的最大特点是算法时间复杂度从通常的o(n)降为o(logn)，此类题型的最大问题，就是超时,TLE(Time Limit Exceeded)。
附上AC代码，编译环境Dev-C&#43;&#43;4.9.9.2
//2013 circle2
//2013 circle
#include &stdio.h&
int main(){
&&& long long n,m,k,x,new_x;
&&& long long circle=1;
&&& scanf(&%lld%lld%lld%lld&,&n,&m,&k,&x);
&&& a=a%n;
&&& while(k&0){
&&&&&&& if(k%2==1)
&&&&&&&&&&& circle=(circle*a)%n;
&&&&&&& k/=2;
&&&&&&& a=(a*a)%n;
&&& m=(m*circle)%n;
&&& new_x=(x&#43;m)%n;//此处new_x=x&#43;m；得分0 ，修改后，得分30
&&& printf(&%lld\n&,new_x);
&&& return 0;
附上90分代码，编译环境Dev-C&#43;&#43;4.9.9.2
//2013 circle2
//2013 circle
#include &stdio.h&
int main(){
&&& long long n,m,k,x,new_x;
&&& long long circle=1;
&&& scanf(&%lld%lld%lld%lld&,&n,&m,&k,&x);
&&& for(i=1;i&=k;i&#43;&#43;){
&&&&&&& circle*=10;
&&&&&&& circle%=n;//每次取余
&&& m=(m*circle)%n;
&&& new_x=(x&#43;m)%n;//此处new_x=x&#43;m；得分0 ，修改后，得分30
&&& printf(&%lld\n&,new_x);
&&& return 0;
附上80分代码，编译环境Dev-C&#43;&#43;4.9.9.2
//2013 circle
#include &stdio.h&
int main(){
&&& int n,m,k,x,new_x;
&&& int circle=1;
&&& scanf(&%d%d%d%d&,&n,&m,&k,&x);
&&& for(i=1;i&=k;i&#43;&#43;){
&&&&&&& circle*=10;
&&&&&&& circle%=n;//每次取余
&&& m=(m*circle)%n;
&&& new_x=(x&#43;m)%n;//此处new_x=x&#43;m；得分0 ，修改后，得分30
&&& printf(&%d\n&,new_x);
&&& return 0;
附上30分代码，编译环境Dev-C&#43;&#43;4.9.9.2
//2013 circle
#include &stdio.h&
int main(){
&&& int n,m,k,x,new_x;
&&& int circle=1;
&&& scanf(&%d%d%d%d&,&n,&m,&k,&x);
&&& for(i=1;i&=k;i&#43;&#43;)
&&&&&&& circle*=10;
&&& circle%=n;
&&& m=(m*circle)%n;
&&& new_x=(x&#43;m)%n;//此处new_x=x&#43;m；得分0 ，修改后，得分30
&&& printf(&%d\n&,new_x);
&&& return 0;
访问：100640次
积分：3343
排名：第11876名
原创：236篇
(2)(4)(10)(22)(11)(4)(3)(9)(10)(12)(41)(3)(27)(21)(26)(4)(8)(19)他的最新文章
他的热门文章
您举报文章：
举报原因：
原文地址：
原因补充：
(最多只允许输入30个字)

我要回帖

更多关于 noip测试数据 的文章

 

随机推荐