[算法竞赛入门经典]数论刷题专栏

例题10-2　不爽的裁判（Disgruntled Judge, NWERC 2008, UVa12169）
有个裁判出的题太难，总是没人做，所以他很不爽。有一次他终于忍不住了，心 想：“反正我的题没人做，我干嘛要费那么多心思出题？不如就输入一个随机数，输出一个 随机数吧。”
于是他找了3个整数x1、a和b，然后按照递推公式xi=(axi-1+b) mod 10001计算出了一个长 度为2T的数列，其中T是测试数据的组数。然后，他把T和x1, x3,…, x2T-1写到输入文件中，x2, x4,…, x2T写到了输出文件中。
你的任务就是解决这个疯狂的题目：输入T, x1, x3,…, x2T-1，输出x2, x4,…, x2T。输入保 证T≤100，且输入的所有x值为0～10000的整数。如果有多种可能的输出，任意输出一个即可。
【分析】
如果知道了a，就可以计算出x2，进而根据x3=(ax2+b) mod 10001算出b。有了x1、a和b， 就可以在O(T)时间内计算出整个序列了。如果在计算过程中发现和输入矛盾，则这个a是非 法的。由于a是0～10000的整数（因为递推公式对10001取模），即使枚举所有的a，时间效 率也足够高。
$$\begin{gathered} x_2=(a{x}_1+b)\%mod⟶a{x}_1+b-k\ast mod=x_2 \\ 同理 \\ 可以得到x_3=(a^2{x}_1+ab+ak\ast mod+b)\%mod⟶x_3=(a^{2}x1+(a+1)b)\%mod \\ 在枚举a的情况下: \\ 可以求得\%mod意义下的((a+1)b)\%mod=(x3-a^2{x}_1\%mod+mod)\%mod=temp \\ (a+1)b-k_1\ast mod=temp \\ 此时b和k_1为未知，利用扩展欧几里得算法g=ext\_gcd(mod,(a+1),k_1,b) \\ 求出b,g,注意这时b可能为负数记得转化为\%mod意义下的数 \\ b=((b\ast temp/g)\%mod+mod)\%mod \\ 最后逐个验证T_1,T_3,....,T_{2n-1}即可 \end{gathered}$$

最后

以上就是曾经信封为你收集整理的[算法竞赛入门经典]数论刷题专栏的全部内容，希望文章能够帮你解决[算法竞赛入门经典]数论刷题专栏所遇到的程序开发问题。

如果觉得靠谱客网站的内容还不错，欢迎将靠谱客网站推荐给程序员好友。