快速幂 NOIP2013 转圈游戏

转圈游戏

题目描述

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 号小伙伴最后走到了第几号位置。

输入输出格式

输入格式:

输入文件名为 circle.in。

输入共 1 行,包含 4 个整数 n、m、k、x,每两个整数之间用一个空格隔开。

输出格式:

输出文件名为 circle.out。

输出共 1 行,包含 1 个整数,表示 10

k 轮后 x 号小伙伴所在的位置编号。

输入输出样例

输入样例#1:

10 3 4 5

输出样例#1:

5

说明

对于 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。

 1 #include<iostream>
 2 #include<cstdio>
 3 #include<cstring>
 4 #include<algorithm>
 5 using namespace std;
 6 int n,m,k,x,ans;
 7 long long ksm(){
 8     long long d=10,rt=1;
 9     while(k){
10         if(k&1) rt=rt*d%n;
11         d=d*d%n;
12         k>>=1;
13     }
14     return rt;
15 }
16 int main(){
17     scanf("%d%d%d%d",&n,&m,&k,&x);
18       ans=ksm()%n*m;
19     ans=(x+ans)%n;
20     printf("%d\n",ans);
21     return 0;
22 }
时间: 05-24

快速幂 NOIP2013 转圈游戏的相关文章

noip2013 转圈游戏

P1965 转圈游戏 625通过 1.8K提交 题目提供者该用户不存在 标签数论(数学相关)递归/分治2013NOIp提高组 难度普及/提高- 提交该题 讨论 题解 记录 最新讨论 洛谷有缺陷 题目描述 n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏.按照顺时针方向给 n 个位置编号,从0 到 n-1.最初,第 0 号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,……,依此类推.游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m

NOIP2013转圈游戏

不得不说NOIP的水题就是牛! 题目简述:给你n个人(0 - n-1) 组成一个环,每次一起前进m步,问编号为x的人在移动了10 ^ k后,他的位置是什么 咱家还能说啥,假设我们把它拉成一个无限长的链,那么每m个长度就是一圈,所以答案就是 (x + m * 10 ^ k) % n 接下来就是快速幂了,记得要时时模就好了,轻松水过~~ #include <algorithm> #include <iostream> #include <cstring> #include

P1965 转圈游戏  快速幂

题目描述 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 号位置. 现

NOIP2013/day1/1/转圈游戏

总时间限制: 10000ms 单个测试点时间限制: 1000ms 内存限制:128000KB 描述 n 个小伙伴(编号从 0 到 n-1)围坐一圈玩游戏.按照顺时针方向给 n 个位置编号,从 0 到 n-1.最初,第 0号小伙伴在第 0 号位置,第 1 号小伙伴在第 1 号位置,……,依此类 推. 游戏规则如下:每一轮第 0 号位置上的小伙伴顺时针走到第 m 号位置,第 1 号位置小伙伴走到第 m+1 号位置,……,依此类推,第n − m号位置上的小伙伴走到第 0 号位置,第n-m+1 号位置上

洛谷P1965 转圈游戏(NOIp2013提高组D1T1)

题目描述 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 号位置. 现

快速幂-(复习)

快速幂要用二分指数的办法来计算, 一般只用把结果取余就可以了 例题 NOIP2013提高组day2第一题 转圈游戏 读题可以知道本题就是求(10^k*m+x)%n 就求10^k%n 可以用记忆化搜索,记得不要dfs两次一样的,设个long long 保存 但也可用直接 用二进制来分解K 一下是最后一种代码 #include <iostream>#include<cstdio>using namespace std;long long n,m,x,k,a=10,ys=1;int ma

数学——快速幂

Wikioi 3285 转圈游戏 题目描述 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 号位置,……,第

3285 转圈游戏

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 号

【66测试20161115】【树】【DP_LIS】【SPFA】【同余最短路】【递推】【矩阵快速幂】

还有3天,今天考试又崩了.状态还没有调整过来... 第一题:小L的二叉树 勤奋又善于思考的小L接触了信息学竞赛,开始的学习十分顺利.但是,小L对数据结构的掌握实在十分渣渣.所以,小L当时卡在了二叉树. 在计算机科学中,二叉树是每个结点最多有两个子结点的有序树.通常子结点被称作“左孩子”和“右孩子”.二叉树被用作二叉搜索树和二叉堆.随后他又和他人讨论起了二叉搜索树.什么是二叉搜索树呢?二叉搜索树首先是一棵二叉树.设key[p]表示结点p上的数值.对于其中的每个结点p,若其存在左孩子lch,则key