关于循环节的推导
Lucaster_
·
2020-01-22 20:07:29
·
个人记录
题目传送门_P1965转圈游戏
首先奉上AC代码 (我知道你们是来看这个的咳咳):
#include
using namespace std;
int k,l,m,n,p,x;
inline int gcd(int a,int b)
{return (b==0)?a:gcd(b,a%b);}
inline int qpow(int a,int b)
{
int ans=1;
while(b)
{
if(b&1) ans=ans*a%p;
a=a*a%p;
b>>=1;
}
return ans%p;
}
int main()
{
cin>>n>>m>>k>>x;
p=n/gcd(n,m);
l=qpow(10,k);
cout<<(x+(m*l))%n;
return 0;
}
(有没有感觉好干净整洁咳咳)
前置芝士：gcd(辗转相除)，快速幂
建议熟练掌握以上两点再食用本题解
Let's start:
读完题，不难看出这个问题是有循环节的，
我们设每经过p次换位可以换回原来的位置，p一定是可求的，而且换位一定是以p次为循环节循环的。
再一看题目中k的范围，(好家伙，这帮人要换10^10^9次位
显然是要找循环节的，而且似乎和gcd(n,m)有关
我写了几个例子（第一个数为n，第二个m）：
10 3；8 6；24 18；45 27；47 5；
没错，我有意根据gcd构造的
发现循环节长度正是楼上大佬们写的那个式子：n/gcd(n,m)
（p.s.是我自己推的!我只是确认一下是不是这个式子才看的题解!）
有些人可能不太明白为什么，这里提供两种方法：
1.显然，手推一下我上面那五组数据（先求一下gcd，再模拟一下具体换位过程，发现次数就是那个式子）就看出来了……
2.（建议自己手画一下）我们设g=gcd(n,m),n=a*g,m=b*g;
首先，我们构造一个长l的区间，l=lcm(n,m),也就是l=a*b*g（lcm与gcd的相互转化）。
具体操作呢，画一条线段，记长度为l，再平均分成几份，每份长度为n，我们可以理解为每次换位不是转圈换，而是往下一段线段里换，（比如说例子中的n=10,m=3,0号第一次换到13，1号换到14，以此类推）那么在这条线段上一定能换到“初始位置”。（因为长为lcm(m,n)的线段一定能令n个人换m次换到初始位置）
用l除以m，就是循环节长度。
（在这条线段上感性理解一下）
根据题设，l=a*b*g,m=b*g，
那么循环节长度就是l/m=a=n/g=n/gcd(n,m)
证毕~
那么现在假设你已经知道循环节长度是怎么推的了，剩下的就很简单了——
我们还可以用这条线段理解，现在我们只需要移动10^k%p（循环节长度）次，也就是在线段上往后移m*(10^k%p)个单位长度
（加一句，如果不用快速幂的话最后一个点会T，亲身试验）
再加上初始位置x，再取个模
答案就是我程序里的最后cout后面那个式子啦！
最后return 0,完结撒花❀
希望我的思路和题解对您有帮助~
(觉得有帮助的留个赞再走呗~)