[Dr.Lib]Minecraft 服务器资源控制策略:AI 抑制而非数量限制

转载自 Minecraft 服务器资源控制策略:AI 抑制而非数量限制 · Phoenix's island

Minecraft 的 lag 问题已经司空见惯,各种控制资源消耗和卡顿的插件也层出不穷。但是它们几乎都非常用力地在一个点上:控制实体数量。

这并不无道理,因为 Minecraft 中最消耗资源的部分就是实体。但是暴力控制实体数量会导致刷怪塔无法正常工作、掉落物清理速度过快等问题,在生存服务器中可能引发玩家的强烈不满。

所以,喵窝开发组从另一个角度做出了一些尝试。

启发

生物实体的数量巨大,主要集中的地区显然不是野外的自然刷怪区,而是玩家聚集的刷怪场、村民工程、动物养殖场等。如果不限制生物的数量和密度同时降低资源消耗,那么只能从生物实体的特性入手了。

Minecraft 最近的版本中引用了 NoAI  的 NBT Tag,带有此标签的生物将不会进行 AI 计算。换句话说,除了占用服务器内存中的一点数据,几乎不会对这个生物实体有任何其他的 CPU 算力消耗。

也就是说,实体消耗的算力资源,绝大部分都是 AI 计算的消耗。

方案

抓上一票人做了一些测试,结果证实生物失去 AI 后大幅降低了 CPU 的算力消耗。这是个 positive 的信号,但是接下来的测试则遇到了问题。

对于养殖场,等生物数量变化不大(或者说只是定期来清理并重新养殖一次)的设施,生物失去 AI 的影响很小,只有在重新繁殖时需要恢复 AI。但是刷怪塔则因为生物没有 AI,同时也被强制不受重力影响而几乎无法使用,即便同时设置 NoGravity 为 false 也无效。

开发组中 @Librazy 提到了 Spigot 的一个参数 nerf-spawner-mobs ,开启时刷怪笼生成的生物将不会拥有 AI,但是会被外界影响(例如水流和火球等)而移动。这个选项是全局的,因此不需要开启,只需要反射 spigot 中设置该功能的方法即可。

经过 @Cylin 查阅Spigot的代码,这个参数会给刷怪笼生成的实体设置 fromMobSpawner = true ,导致实体的 doTick()中跳过实体的AI处理。

于是整个方案的流程便是当服务器卡顿时抑制生物密集区的生物 AI 从而降低资源占用,同时最大程度上保证玩家对生物的需求。「服务器卡顿」的考量以服务器 TPS 而非实体数量为准,当服务器 TPS 高于一定值时即认为服务器没有超负荷,不会有任何操作,最大程度上利用硬件的性能。

实现

插件主要由开发组的 @Cylin 编写,源代码以 MIT 协议发布在 GitHub 上。

插件每隔一段时间扫描服务器的 TPS 确认运行状况,如果 TPS 低于阈值则触发 AI 控制,TPS 高于一定值且持续一段时间即认为服务器已恢复正常运行状态,自动恢复被抑制的实体 AI 减少对生存体验的影响。

实现过程中额外添加了一些额外可能被生存服务器用到的功能:

  • per-world 控制,如果玩家需要建造以仇恨为基础的小黑塔,可以关闭对末地的控制。
  • 实体总量和单区块实体密度在 AI 抑制时纳入考虑,更加精准抑制资源消耗较高的区块。

测试

yasui 插件在 毛玉線圈物語 服务器中应用测试。由于近期玩家数量爆炸式增长(日常在线 5 人到 ~30 人甚至 50 人),各种实体控制插件均告无效。yasui 插件应用后被证实数次发挥作用,没有任何实体数量限制的前提下将服务器 TPS 稳定在 19 以上,服务器实体承载数量从 ~2500 提到至接近 5000,并且还有继续提高的可能(数次触发中最高一次单世界实体记录是 4808,其他世界中仍有大约 2000 实体未被计入)。

吐槽:你们贼能刷

Functional Programming For The Rest Of Us

Via https://github.com/justinyhuang/Functional-Programming-For-The-Rest-of-Us-Cn/blob/master/FunctionalProgrammingForTheRestOfUs.cn.md

傻瓜函数式编程

2006年6月19日,星期一

开篇

我们这些码农做事都是很拖拉的。每天例行报到后,先来点咖啡,看看邮件还有RSS订阅的文章。然后翻翻新闻还有那些技术网站上的更新,再过一遍编程论坛口水区里那些无聊的论战。最后从头把这些再看一次以免错过什么精彩的内容。然后就可以吃午饭了。饭饱过后,回来盯着IDE发一会呆,再看看邮箱,再去搞杯咖啡。光阴似箭,可以回家了……
(在被众人鄙视之前)我唯一想说的是,在这些拖拉的日子里总会时不时读到一些不明觉厉的文章。如果没有打开不应该打开的网站,每隔几天你都可以看到至少一篇这样的东西。它们的共性:难懂,耗时,于是这些文章就慢慢的堆积成山了。很快你就会发现自己已经累积了一堆的收藏链接还有数不清的PDF文件,此时你只希望隐入一个杳无人烟的深山老林里什么也不做,用一年半载好好的消化这些私藏宝贝。当然,我是说最好每天还是能有人来给送吃的顺带帮忙打扫卫生倒垃圾,哇哈哈。

我不知道你都收藏了些什么,我的阅读清单里面相当大部分都是函数式编程相关的东东:基本上是最难啃的。这些文章充斥着无比枯燥的教科书语言,我想就连那些在华尔街浸淫10年以上的大牛都无法搞懂这些函数式编程(简称FP)文章到底在说什么。你可以去花旗集团或者德意志银行找个项目经理来问问1:你们为什么要选JMS而不用Erlang?答案基本上是:我认为这个学术用的语言还无法胜任实际应用。可是,现有的一些系统不仅非常复杂还需要满足十分严苛的需求,它们就都是用函数式编程的方法来实现的。这,就说不过去了。
关于FP的文章确实比较难懂,但我不认为一定要搞得那么晦涩。有一些历史原因造成了这种知识断层,可是FP概念本身并不难理解。我希望这篇文章可以成为一个“FP入门指南”,帮助你从指令式编程走向函数式编程。先来点咖啡,然后继续读下去。很快你对FP的理解就会让同事们刮目相看了。

什么是函数式编程(Functional Programming,FP)?它从何而来?可以吃吗?倘若它真的像那些鼓吹FP的人说的那么好,为什么实际应用中那么少见?为什么只有那些在读博士的家伙想要用它?而最重要的是,它母亲的怎么就那么难学?那些所谓的closure、continuation,currying,lazy evaluation还有no side effects都是什么东东(译者:本着保留专用术语的原则,此处及下文类似情形均不译)?如果没有那些大学教授的帮忙怎样把它应用到实际工程里去?为什么它和我们熟悉的万能而神圣的指令式编程那么的不一样?
我们很快就会解开这些谜团。刚才我说过实际工程和学术界之间的知识断层是有其历史原因的,那么就先让我来解释一下这个问题。答案,就在接下来的一次公园漫步中:

继续阅读 "Functional Programming For The Rest Of Us" »

[Dr.Lib]Note:Algorithm – 莫队算法

莫队算法:对于两个区间的查询[l1,r1] ,[l2,r2]如果每增加一个区间元素或者删除,都能做到O(1)的话
那么从[l1,r1]转移到[l2,r2],暴力可以做到|l1-l2|+|r1-r2|,就是manhattan距离
莫队的论文一直没有找到,所以只是大致的了解下,应该是证明出构造出哈密尔顿路径是最优的。
但是可以用manhattan mst来构造,大约会是两倍,然后莫队证明出这样转移的上限是O(n*sqrt(n))。
所以对于这种无修改的区间查询来说
可以先将所有的区间,看成二维平面上的点,求一次manhattan mst,然后根据mst来进行转移
相邻的两个区间的查询转移,暴力解决。

Via http://blog.csdn.net/huzecong/article/details/8576908

http://blog.csdn.net/acm_cxlove/article/details/8894431

在此感谢

据说这个算法是莫涛提出的(Orz!),但是在网上到处都搜不到相关资料,最后问pty才知道的。这个算法是用于处理一类不带修改的区间查询问题的离线算法,其核心在于利用曼哈顿距离最小生成树算法对区间处理顺序进行处理。比如下面这个例题(清橙A1206《小Z的袜子》,就是莫队出的题):

给定一个长为N的序列,每个元素的值是其颜色。有M次询问,每次询问从一个区间中随机选取两个元素同色的概率。

一次询问[l,r]的答案即,其中是区间中第i中颜色的个数。显然暴力是O(NM)的,而且一般的区间问题的思路似乎不适用。

我们先考虑一个简化的问题:所有的查询区间的左端点都是1。那么我们可以按右端点排序,假设已经处理出了[1,r]的答案,考虑转移到[1,r+k],即添加k个元素,这个可以在O(k)的复杂度内求出。那么处理所有区间的复杂度(不考虑排序)就是O(N)。

那么如果是从[l,r]转移到[l’,r’]呢?复杂度即O(|r’-r|+|l’-l|),也即点(l,r)到点(l’,r’)的曼哈顿距离。那么如果将所有询问转化成二维平面中的点,求曼哈顿距离最小生成树,再按照生成树的顺序做,就可以最小化区间之间转移的复杂度。可以证明(我不会证……似乎莫队的论文里有),这样做的复杂度是O(N1.5)的。问题也就得到了解决。

[Dr.Lib]Note:Math – \(\Sigma \frac{1}{n^{2}}\)

转载自http://www.ivy-end.com/archives/1098


今天我们来介绍一个曾经在数列题中做过无数遍的数列\(a_{n}=\frac{1}{n^{2}}\),为了方便下文的讨论,我们记\(S_{n}\)为数列\(a_{n}\)的前\(n\)项和。我们做过最熟悉的题目莫过于证明\(S_{n}<2\),这个证明对于大家来说应该是非常容易的\[S_{n}=\sum_{i=1}^{n}\frac{1}{i^{2}}=1+\sum_{i=2}^{n}\frac{1}{i\cdot\left(i-1 \right )}=2-\frac{1}{n}.\]

那么大家是否考虑过,\(\lim_{n \to \infty }S_{n}\)究竟等于多少?我记得严桂华讲过欧拉曾经计算过这个问题,今天在国外一个数学讨论网站上翻到了一篇关于如何计算\(\lim_{n \to \infty }S_{n}\)的问答(原文地址)。在此仅介绍几种方法。

首先给出结果,再用多种方法进行证明\[\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}.\]不得不说,这一结果是非常不可思议的,因为它居然包含了\(\pi\)。读者如果不相信的话,可以自行计算一下,当\(n\)趋向于正无穷时,答案便越接近\(\frac{\pi^{2}}{6}\)。

好了,废话不说,我们进入证明部分。

法一:

当\(0<x<\frac{\pi}{2}\)时,有\(0<\sin{x}<x<\tan{x}\)。至于这个命题的证明,请参考下图:

Mathematics 003-1-1

这样,我们可以得到\[\frac{1}{\tan^{2}{x}}<\frac{1}{x^{2}}<\frac{1}{\sin^{2}{x}}.\]我们知道,\(\frac{1}{\tan^{2}{x}}=\frac{1}{\sin^{2}{x}}-1\)(很容易由三角恒等式导出)。将区间\(\left(0,\frac{\pi}{2}\right)\)等分成\(2^{n}\)个部分,令\(x_{k}=\frac{\pi}{2}\cdot\frac{k}{2^{n}}\),并将不等式两边对\(x_{k}\)进行求和,可以得到\[\sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k} – \sum_{k=1}^{2^n-1} 1 < \sum_{k=1}^{2^n-1} \frac{1}{x_k^2} < \sum_{k=1}^{2^n-1} \frac{1}{\sin^2 x_k}.\]我们不妨将不等式右边的表达式记为\(T_{n}\),那么原不等式可以化简为\[T_{n} – \left(2^n – 1\right) < \sum_{k=1}^{2^n-1} \left( \frac{2 \cdot 2^n}{\pi} \right)^2 \frac{1}{k^2} < T_n.\]接下来我们主要考察\(T_{n}\)。它看起来是一个非常复杂的求和,实际上可以非常简单的计算出来。首先,我们考虑下面的式子\[\frac{1}{\sin^2 x} + \frac{1}{\sin^2 (\frac{\pi}{2}-x)} = \frac{\cos^2 x + \sin^2 x}{\cos^2 x \cdot \sin^2 x} = \frac{4}{\sin^2 2x}.\]因此,如果我们将\(T_{n}\)以\(\frac{\pi}{4}\)为中点进行配对(选取区间\(\left(0,\frac{\pi}{2}\right)\)左边的点\(x_{k}\),与右边的点\(\frac{\pi}{2}-x_{k}\)),考虑递推,再加上中点\(\frac{1}{\sin^{2}{\frac{\pi}{4}}}=2\),则可以得到\[T_{n}=4T_{n-1}+2.\]又\(T_{1}=2\),我们可以很容易的得到\(T_{n}\)的通项公式\[T_n = \frac{2(4^n-1)}{3}.\]于是,我们得到了这样的不等式\[\frac{2(4^n-1)}{3} – (2^n-1) \leq \frac{4^{n+1}}{\pi^2} \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq \frac{2(4^n-1)}{3}.\]两边同时乘以\(\frac{\pi^{2}}{4^{n+1}}\)使得不等式的中间与我们的目标形式更加相似,这样我们又得到一个不等式\[\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3} – (2^n-1) \leq \sum_{k=1}^{2^n-1} \frac{1}{k^2} \leq\frac{\pi^{2}}{4^{n+1}} \cdot \frac{2(4^n-1)}{3}.\]当\(n\rightarrow\infty\)时,不等式左右两边同时趋向于\(\frac{\pi^{2}}{6}\),由夹逼准则得\(\lim_{n \to \infty }S_{n}=\frac{\pi^{2}}{6}\)。证毕。

法二:

我们可以借助函数\(f\left(x\right)=x^{2},x\in\left[-\pi,\pi\right]\)来找到它对应的三角傅立叶级数\[\frac{a_{0}}{2}+\sum_{n=1}^{\infty }(a_{n}\cos nx+b_{n}\sin x),\]且它是周期收敛的。

又\(f\left(x\right)\)为偶函数,这足够让我们得到它的系数\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\cos nx\;dx\qquad n=0,1,2,3,\cdots,\]因为\[b_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }f(x)\sin nx\;dx=0\qquad n=1,2,3,\cdots.\]令\(n=0\)得\[a_{0}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}dx=\frac{2}{\pi }\int_{0}^{\pi}x^{2}dx=\frac{2\pi ^{2}}{3}.\]当\(n=1,2,3,\cdots\)时,我们有\[a_{n}=\frac{1}{\pi }\int_{-\pi }^{\pi }x^{2}\cos nx\;dx\\=\frac{2}{\pi }\int_{0}^{\pi }x^{2}\cos nx\;dx=\frac{2}{\pi }\times \frac{2\pi }{n^{2}}(-1)^{n}=(-1)^{n}\frac{4}{n^{2}},\]因为\[\int x^2\cos nx\;dx=\frac{2x}{n^{2}}\cos nx+\left( \frac{x^{2}}{n}-\frac{2}{n^{3}}\right) \sin nx.\]因此\[f(x)=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos nx\right).\]又\(f\left(\pi\right)=\pi^{2}\),我们可以得到\[\pi ^{2}=\frac{\pi ^{2}}{3}+\sum_{n=1}^{\infty }\left( (-1)^{n}\frac{4}{n^{2}}\cos \left( n\pi \right) \right)\]即\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\left( (-1)^{n}(-1)^{n}\frac{1}{n^{2}}\right)\]进一步化简得\[\pi ^{2}=\frac{\pi ^{2}}{3}+4\sum_{n=1}^{\infty }\frac{1}{n^{2}}.\]因此\[\sum_{n=1}^{\infty }\frac{1}{n^{2}}=\frac{\pi ^{2}}{4}-\frac{\pi ^{2}}{12}=\frac{\pi ^{2}}{6}.\]证毕。

法三:

当\(x=0\)时\(\sin{x}\)可以使用泰勒级数展开\[\sin x = x – \frac{x^3}{3!}+\frac{x^5}{5!}-\frac{x^7}{7!}+\cdots.\]于是我们可以得到\[\frac{x^3}{3!}=x\left(\frac{x^2}{\pi^2} + \frac{x^2}{2^2\pi^2}+ \frac{x^2}{3^2\pi^2}+\cdots\right)=x^3\sum_{n=1}^{\infty}\frac{1}{n^2\pi^2},\]即\[\sum_{n=1}^\infty\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法四:

设\(z\)为复数,考虑\[\frac{\pi^2}{\sin^2\pi z}=\sum_{n=-\infty}^{\infty}\frac{1}{(z-n)^2}\]由复变函数分析可得\[\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}=\sum_{n=1}^{\infty}\frac{1}{(z-n)^2}+\sum_{n=1}^{\infty}\frac{1}{(z+n)^2}.\]这样,当右边\(z=0\)时,我们就可以得到\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=2\sum_{n=1}^{\infty}\frac{1}{n^2}.\]又\[\lim_{z\to 0}\left(\frac{\pi^2}{\sin^2\pi z}-\frac{1}{z^2}\right)=\frac{\pi^2}{3}.\]因此\[\sum_{n=1}^{\infty}\frac{1}{n^2}=\frac{\pi^2}{6}.\]证毕。

法五:

这是欧拉的方法。令\[s=\sin^{-1}{x}.\]那么\[\int_{0}^{\frac{\pi}{2}}sds=\frac{\pi^{2}}{8}.\]但是\[\int\limits_0^1 {\frac{{{{\sin }^{ – 1}}x}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{{\pi ^2}}}{8}.\]又\[{\sin ^{ – 1}}x = \int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} = x + \frac{1}{2}\frac{{{x^3}}}{3} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5} + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{{{x^7}}}{7} + \cdots.\]我们可以得到\[\int\limits_0^1 {\left\{ {\frac{{dx}}{{\sqrt {1 – {x^2}} }}\int {\frac{{dx}}{{\sqrt {1 – {x^2}} }}} } \right\}} = \int\limits_0^1 {\left\{ {x + \frac{1}{2}\frac{{{x^3}}}{3}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{{{x^5}}}{5}\frac{{dx}}{{\sqrt {1 – {x^2}} }} + \cdots } \right\}}.\]但是\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{2n}}{{2n + 1}}\int\limits_0^1 {\frac{{{x^{2n – 1}}}}{{\sqrt {1 – {x^2}} }}dx}.\]这样,可以得到\[\int\limits_0^1 {\frac{{{x^{2n + 1}}}}{{\sqrt {1 – {x^2}} }}dx} = \frac{{\left( {2n} \right)!!}}{{\left( {2n + 1} \right)!!}}.\]又所有的次数都是奇数,所以最终的结果为\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{2}\frac{1}{3}\left( {\frac{2}{3}} \right) + \frac{{1 \cdot 3}}{{2 \cdot 4}}\frac{1}{5}\left( {\frac{{2 \cdot 4}}{{3 \cdot 5}}} \right) + \frac{{1 \cdot 3 \cdot 5}}{{2 \cdot 4 \cdot 6}}\frac{1}{7}\left( {\frac{{2 \cdot 4 \cdot 6}}{{3 \cdot 5 \cdot 7}}} \right) \cdots,\]\[\frac{{{\pi ^2}}}{8} = 1 + \frac{1}{{{3^2}}} + \frac{1}{{{5^2}}} + \frac{1}{{{7^2}}} + \cdots.\]令\[1 + \frac{1}{{{2^2}}} + \frac{1}{{{3^2}}} + \frac{1}{{{4^2}}} + \cdots = \omega.\]则\[\frac{1}{{{2^2}}} + \frac{1}{{{4^2}}} + \frac{1}{{{6^2}}} + \frac{1}{{{8^2}}} + \cdots = \frac{\omega }{4}.\]这样,我们可以得到\[\frac{\omega }{4} + \frac{{{\pi ^2}}}{8} = \omega.\]即\[\omega = \frac{{{\pi ^2}}}{6}.\]证毕。

法六:

\[\sum_{i=1}^{n}\frac{1}{i^{2}}=\zeta(2)=\frac{4}{3}\sum_{n=0}^{+\infty}\frac{1}{(2n+1)^2}=\frac{4}{3}\int_{0}^{1}\frac{\log y}{y^2-1}dy\]\[=\frac{2}{3}\int_{0}^{1}\frac{1}{y^2-1}\left[\log\left(\frac{1+x^2 y^2}{1+x^2}\right)\right]_{x=0}^{+\infty}dy=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{x}{(1+x^2)(1+x^2 y^2)}dx\,dy\]
\[=\frac{4}{3}\int_{0}^{1}\int_{0}^{+\infty}\frac{dx\, dz}{(1+x^2)(1+z^2)}=\frac{4}{3}\cdot\frac{\pi}{4}\cdot\frac{\pi}{2}=\frac{\pi^2}{6}.\]证毕。

就介绍这几种方法吧,大家可以有选择的进行阅读。以后数学作业中再有证明\(S_{n} < 2\)的时候,不妨这样写\(\lim_{n \to \infty }S_{n}=\frac{\pi}{6} < 2\),怕老师不承认,可以顺便证明一下,至于给不给分,就不好说了。

 

[Dr.Lib]Note:Math – Extend Baby Step Giant Step

这种数学题都是转AC大神的……以及Seter

http://hi.baidu.com/aekdycoin/item/236937318413c680c2cf29d4

http://seter.is-programmer.com/posts/32188.html

Baby Step Giant Step

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{P}\]

求解x,我们可以做一个等价

\[x = i\ast m + j  ( 0 \leq i,j< m) ,m = \lceil \sqrt{C} \rceil\]

而这么分解的目的无非是为了转化为:

\[(A^{i})^{m} * A^{j} = B \mod C\]

之后做少许暴力的工作就可以解决问题:
(1) for i = 0 -> m, 插入\( Hash (A^i \mod C, i) \)

(2) 枚举 i ,对于每一个枚举到的i,令  \( {A}' = (A^m)^i \mod C\)
我们有\[A' * A^j = B \mod C\]

显然\(A'B,C\),均已知,而由于C为素数,那么(AA,C)无条件为1

令\(p=(A^M)^i \mod C,x=A^j \mod C\)则\(p*x=B\mod C\)。

我们从0开始枚举i直到i*M超过C-1,则相当于知道了p,要求x。

由于 (A',C)=1 ,于是对于这个模方程解的个数唯一(可以利用扩展欧几里得或 欧拉定理来求解)

那么对于得到的唯一解x,在Hash表中寻找(x,j),如果找到,则返回  \(i*m+j>0\) 。

如果需要得到 x > 0的解,那么只需要在上面的步骤中判断 当 \(i*m+j>0\) 的时候才返回。

扩展Baby Step Giant Step

\[A^{x}=B (\mod C) 0\leq x <C,C\in \mathbb{N^*}\]

当C不是素数的时候能否直接套用呢?当然不可以……最直接的问题就是,不一定存在逆元!

考虑一个\(G'\)同时是ABC的因数,令\(B'=\frac{B}{G'},C'=\frac{C}{G'}\),则当x不等于0时,

\(\frac{A}{G'}*A^(x-1)=B'\mod  C'\)。

这样多弄几次,C的因数就越来越少,直到(A,C)=1。

那么如何选取\(G'\)呢?AC大神告诉你:不断取\(G'=gcd(A,C')\),直到\(G'\)=1。如果任意一个\(G'\)不是\(B'\)的因数则一定无解。

假设取了r次\(G'\),然后所有\(G'\)的积是G,则问题变为\(\frac{A^r}{G}*A^{x-r}=B'\mod C'\),令\(D=\frac{A^r}{G}\)(一定是整数),则由于此时\((A,C')=1\),所以\((D,C')=1\)。

那么上面算法中只要变成求\(D\)对于\(C'\)的逆元就可以了,返回的答案还要加上r。

还有一点小问题,就是这样得出的答案是大于等于r的。但是即使每次\(G'=2\),r最大也只有\(log_{2}C\),那么这些再暴力求解就可以了。