Blog of Xay

昨天去工学部上选修课，于是又走出校门去看东湖。东湖的浩大和宽阔吸引了我。在东湖边上踱步，思绪纷繁，感触良多。为什么这一望无边的景象总能让人流连忘返呢？ 它到底给了我们什么震撼，还是给了我们什么安慰？ 我无可猜测，只是想像着自己是一条在大海中梦游的小鱼...

r^2 mod n = x (0<=r<n, 1<=x<n)
给定x和n(2<=n<10^9),求所有r
其中r的一个解r0已经给出

由题意知：r^2 = x + n*k (1)
又可得    r0^2=x + n*k0 (2)
(1)(2)式相减得(r+r0)*(r-r0) = n * (k - k0)，即(r+r0)*(r-r0) = n * p (p != 0)

现在将n分解为两个数x1*x2的积
(x1，x2由O(n^(1/2))的枚举得到)
则可得到方程组 r + r0 = x1 * s1
                       r - r0 = x2 * s2
将两式相减得：x1 * s1 - x2 * s2 = 2 * r0
其中r0, x1, x2已知，于是问题转化为一元二次不定方程
用扩展的欧几里德解出该方程，将s1,s2带回方程组中求得r，再用r^2 mod n = x检验正误
最后有序输出结果即可

答：幸福就是遭罪。。

用C++写了一个支持括号，加减乘除的计算器（命令版），请同志们帮忙测试一下

输入仅允许数字，小数点，运算符和括号，注意：不允许有空格（可以输入空格测试一下）

谢谢支持~

点此下载

刚一开始我看了几道题，发现I题比较水，于是直接敲I题。期间有人过了A和C题，25分钟，我全场第一个过了I。紧接着我去做A题，也是简单题，枚举就ok，理解错误，WA了2次之后AC。然后我跟风做C题，很经典的DP，我把它想简单了，于是用了个n^2(n<300)的办法，果然WA了，不过后来我找到了错误数据，改成n^3的dp就过了。接着就是本场最让我纠结的一题，使用了错误的解法，使用了枚举法，使用了打表法，大概用了2个半小时，最后用组合法才算勉强过了这题。然后F题是找到结果就行了。

总得来说，题目难度不大。我的水平还有待提高，难题不会做，简单题又做得慢，很囧很无奈。

于是我去吃饭了。