开发者社区> pushytao> 正文

转圈游戏——UPC

简介: 题目描述 暑假开始了,夏令营的日子也来临了。住进宿舍的第一天晚上,小A和新认识的同学们在宿舍里玩起了转圈游戏。编号为0n-1的n个小伙伴围成一圈,他们坐的位置也被编号为了0n-1。最初,第0号小伙伴在第0号位置,第1号小伙伴在第1号位置…依此类推。 游戏规则如下:每一轮第0号位置上的小伙伴顺时针走到第m号位置,第1号位置小伙伴走到第m+1号位置…依此类推,第n−m号位置上的小伙伴走到第0号位置,第n-m+1 号位置上的小伙伴走到第1号位置…第n-1号位置上的小伙伴顺时针走到第m-1号位置。 这个游戏实在太好玩了,以至于小A和他的小伙伴们玩了10^k轮,请问x号小伙伴最后走到了第几号位置。
+关注继续查看

题目描述


暑假开始了,夏令营的日子也来临了。住进宿舍的第一天晚上,小A和新认识的同学们在宿舍里玩起了转圈游戏。编号为0n-1的n个小伙伴围成一圈,他们坐的位置也被编号为了0n-1。最初,第0号小伙伴在第0号位置,第1号小伙伴在第1号位置…依此类推。


游戏规则如下:每一轮第0号位置上的小伙伴顺时针走到第m号位置,第1号位置小伙伴走到第m+1号位置…依此类推,第n−m号位置上的小伙伴走到第0号位置,第n-m+1 号位置上的小伙伴走到第1号位置…第n-1号位置上的小伙伴顺时针走到第m-1号位置。


这个游戏实在太好玩了,以至于小A和他的小伙伴们玩了10^k轮,请问x号小伙伴最后走到了第几号位置。


输入


第一行有四个由单个空格分隔的整数n,m,k,x,意义如题所示。


输出


仅一行一个整数,表示10^k轮后第x号小伙伴的最终位置编号。


样例输入 Copy


10 3 4 5


样例输出 Copy


5


提示


对于30%的数据,0 < k < 7;

对于80%的数据,0 < k < 10^7;

对于100%的数据,1 <n < 1,000,000,0 < m < n,0 ≤ x < n,0 < k < 10^9


式子不难推导

( x+ m10k )%n

=(x%n+m%n10k%n)%n


#pragma GCC optimize("Ofast,unroll-loops,no-stack-protector,fast-math")
#pragma GCC optimize("Ofast")
#pragma GCC target("sse,sse2,sse3,ssse3,sse4,popcnt,abm,mmx,avx,tune=native")
#pragma comment(linker, "/stack:200000000")
#pragma GCC optimize (2)
#pragma G++ optimize (2)
#include <bits/stdc++.h>
#include <algorithm>
#include <map>
#include <queue>
#include <set>
#include <stack>
#include <string>
#include <vector>
using namespace std;
#define wuyt main
typedef long long ll;
#define HEAP(...) priority_queue<__VA_ARGS__ >
#define heap(...) priority_queue<__VA_ARGS__,vector<__VA_ARGS__ >,greater<__VA_ARGS__ > >
template<class T> inline T min(T &x,const T &y){return x>y?y:x;}
template<class T> inline T max(T &x,const T &y){return x<y?y:x;}
ll read(){ll c = getchar(),Nig = 1,x = 0;while(!isdigit(c) && c!='-')c = getchar();
if(c == '-')Nig = -1,c = getchar();
while(isdigit(c))x = ((x<<1) + (x<<3)) + (c^'0'),c = getchar();
return Nig*x;}
#define read read()
const ll inf = 1e15;
const int maxn = 1e6 + 7;
const int mod = 1e9 + 7;
ll n,m,k,x;
ll superpow(ll a,ll b){
    ll ans=1;
    while (a>0)
    {
        if (a%2) ans=ans*b%n;
        b=b%n*b%n;
        a/=2;
    }
    return ans;
}
int main(){
    n=read,m=read,k=read,x=read;
    ll res=superpow(k,10);
    res*=m;
    res%=n;
    res+=x;
    res%=n;
    cout<<res<<endl;
    return 0;
}


版权声明:本文内容由阿里云实名注册用户自发贡献,版权归原作者所有,阿里云开发者社区不拥有其著作权,亦不承担相应法律责任。具体规则请查看《阿里云开发者社区用户服务协议》和《阿里云开发者社区知识产权保护指引》。如果您发现本社区中有涉嫌抄袭的内容,填写侵权投诉表单进行举报,一经查实,本社区将立刻删除涉嫌侵权内容。

相关文章
阿里云服务器怎么设置密码?怎么停机?怎么重启服务器?
如果在创建实例时没有设置密码,或者密码丢失,您可以在控制台上重新设置实例的登录密码。本文仅描述如何在 ECS 管理控制台上修改实例登录密码。
23538 0
阿里云服务器ECS远程登录用户名密码查询方法
阿里云服务器ECS远程连接登录输入用户名和密码,阿里云没有默认密码,如果购买时没设置需要先重置实例密码,Windows用户名是administrator,Linux账号是root,阿小云来详细说下阿里云服务器远程登录连接用户名和密码查询方法
22248 0
如何设置阿里云服务器安全组?阿里云安全组规则详细解说
阿里云安全组设置详细图文教程(收藏起来) 阿里云服务器安全组设置规则分享,阿里云服务器安全组如何放行端口设置教程。阿里云会要求客户设置安全组,如果不设置,阿里云会指定默认的安全组。那么,这个安全组是什么呢?顾名思义,就是为了服务器安全设置的。安全组其实就是一个虚拟的防火墙,可以让用户从端口、IP的维度来筛选对应服务器的访问者,从而形成一个云上的安全域。
18878 0
使用SSH远程登录阿里云ECS服务器
远程连接服务器以及配置环境
14701 0
阿里云服务器ECS登录用户名是什么?系统不同默认账号也不同
阿里云服务器Windows系统默认用户名administrator,Linux镜像服务器用户名root
15556 0
腾讯云服务器 设置ngxin + fastdfs +tomcat 开机自启动
在tomcat中新建一个可以启动的 .sh 脚本文件 /usr/local/tomcat7/bin/ export JAVA_HOME=/usr/local/java/jdk7 export PATH=$JAVA_HOME/bin/:$PATH export CLASSPATH=.
14870 0
阿里云服务器如何登录?阿里云服务器的三种登录方法
购买阿里云ECS云服务器后如何登录?场景不同,云吞铺子总结大概有三种登录方式: 登录到ECS云服务器控制台 在ECS云服务器控制台用户可以更改密码、更换系统盘、创建快照、配置安全组等操作如何登录ECS云服务器控制台? 1、先登录到阿里云ECS服务器控制台 2、点击顶部的“控制台” 3、通过左侧栏,切换到“云服务器ECS”即可,如下图所示 通过ECS控制台的远程连接来登录到云服务器 阿里云ECS云服务器自带远程连接功能,使用该功能可以登录到云服务器,简单且方便,如下图:点击“远程连接”,第一次连接会自动生成6位数字密码,输入密码即可登录到云服务器上。
36366 0
+关注
312
文章
0
问答
文章排行榜
最热
最新
相关电子书
更多
JS零基础入门教程(上册)
立即下载
性能优化方法论
立即下载
手把手学习日志服务SLS,云启实验室实战指南
立即下载