2013 转圈问题
题面
说实话,这道题卡博主挺长时间的(可能是博主太菜了的缘故)
首先看到这道题,第一反应就是找到0这个的点究竟需要几次轮回才能回到自己的初始位置,显然,很麻烦,而且,这个思路我也不会实现…………
之后,我旁边的chdy忍不了我了,就把思路告诉了我(因为已经快要省选了,显然不能在这种水题上浪费时间)。
思路
当轮多少多少轮之后也就是他走了多少多少的m个长度,这样子思路就有了,如上面的样例,一共有10个人,0~9的坐标,轮了10^4之后,也就是走了310 ^4那么长的距离,这样我们就可以直接找到要求的内个坐标行走的距离,即x+m10 ^k(5+3*10 ^4),然后我们用行走的距离%上一共的人数,那么此时你%出来的结果便是最后的在x位置上的值;
重要的是,在这里10 ^k怎么求(这里会涉及到快速幂的知识,在代码下面会有补充)
而且,这时10 ^k过大怎么办,这个时候就要用到同模定理,推一下我的博客https://blog.****.net/qq_43093454/article/details/83786116(这上面有)
上ac代码
#include<bits/stdc++.h>
using namespace std;
int n,m,k,x;
int ans=1;
void kuaisumi(int y)
{
int base=10;
while(y!=0)
{
if(y%2!=0) ans=(ans*base)%n;//这里注意都要%n的
base=(base*base)%n;//注意注意
y=y/2;
}
}
int main()
{
scanf("%d%d%d%d",&n,&m,&k,&x);
kuaisumi(k);
ans=(x+m*ans)%n;
cout<<ans<<endl;
return 0;
}
补充(快速幂)
这里博主简而言之,就是把指数搞成二进制,然后输出,让我转载一个比较靠谱的人的博客,博主就照搬一个
int power(int a,int b)
{
int r=1,base=a;
while(b!=0)
{
if(b%2) r*=base;
base*=base;
b/=2;
}
return r;
}
来自https://blog.****.net/karen_yu_/article/details/78688349的博客,超级赞!!!!!!