Java教程

P1965 [NOIP2013 提高组] 转圈游戏

本文主要是介绍P1965 [NOIP2013 提高组] 转圈游戏，对大家解决编程问题具有一定的参考价值，需要的程序猿们随着小编来一起学习吧！

Problem

给定\(n,m,k,x\)，\(x\)每次会变成\((x + m) \bmod n\)，称为1次变换，求经过\(10^k\)次变换后\(x\)的值。
\(n \le 10^6,m < n,k,x \le 10^9\)。

Solution

看见\(n\)数据范围显然可以想到整循环节，但是我们不会推，咋办，发现求循环节至多\(\mathcal{O}(n)\)，求完之后相当于求\(10^k \bmod t\)所对应的值，\(t\)即循环节长度，所以时间复杂度为\(\mathcal{O}(n + \log{k})\)，不过\(t\)好像是可以\(\mathcal{O}(1)\)。

这篇关于P1965 [NOIP2013 提高组] 转圈游戏的文章就介绍到这儿，希望我们推荐的文章对大家有所帮助，也希望大家多多支持为之网！
您可能喜欢
栏目导航