基本上一整天都待在数实。真的挺无聊的。。如果没有人陪着就更无聊了吧。已经开始玩MC了不知道接下来会怎么样。数实这种东西就偶尔来一次兴奋不已，整天待着就无聊的要死了。

跟假期在家里百无聊赖一个意思。

CP真是为了奖金不择手段。

WTF。

早上还是学了点东西的。

扩展GCD、中国剩余定理、高斯消元以及解xor方程组、大步小步算法、线性筛、pollard-rho。

扩展gcd没什么好说的。理解起来一点难度都没有，能自己推出来的。

-----------------------------------------------------------------

高斯消元就跟平时解方程一个意思。把平时的过程一般化就是高斯消元了。

xor方程大同小异，把+/-运算变成xor就行了。

如果出现[0 0 0 0 0 0|0]那么就说明有冗余方程。如果出现[0 0 0 0 0 0 0|x](x!=0)那么说明无解。

如果消元到最后产生的上三角矩阵的行数比列数小，即有效方程数小于未知数的数量，那么就产生自由元。自由元只是一个相对的概念。一个方程组的自由元数量是一定的，但是自由元的选取方案不唯一。

对于xor方程组来说一个自由元意味着方程组解的数量*2.

-----------------------------------------------------------------

中国剩余定理的模板题小学的时候经常被作为奥术题，我还都做不出来。事情是这样的。方程组由{x=bi(mod ci)}组成。令M=c1*c2...*cn。对于第i条方程来说我们试图寻找这么一个di使得：di=k*(M/ci)，且di=1(mod ci)。设di=1+y*ci，那么方程变成：k*(M/ci)=y*ci+1。想办法解这玩意就可以得到一个k，那么di=k*(M/ci)。那么x=sigma(di*bi) Mod M就是方程的一个解。这也蛮明显的。构造性的算法真心巧妙。

-----------------------------------------------------------------

大步小步算法是个很暴力的东西。用来求x使得a^x=b(mod p)的。

如果p是质数，或者说p与a互质，那么：

任意取一自然数m(m<=p)。可令x=k*m-r，其中(m>r>=0)。代入方程：a^(k*m)=b*(a^r)(mod p)。

将r从0循环到m-1，计算出所有b*(a^r)(mod p)，然后把每一个取值所对应的r存在一个哈希表里。如果p比较大就开map，如果p比较小就直接用数组把。并且这个取值和r不是一一对应的，但是这并无大碍。然后计算a^m，并且将k从1循环到(p/m)，对于每一个k计算出a^(k*m)，然后在哈希表中寻找有没有对应的r存在。如果存在那么就找到了一个解x=k*m-r。

如果用map做哈希表：效率O((m+n/m)logm)。在m=[sqrt(n)]时效率最高。

这种分块求解【或者说大步小步】的思想很有用。

-----------------------------------------------------------------

线性筛：

先上代码

#define NN 100000
#define PRIME_IN_N 5000
bool flag[NN];
int prime[PRIME_IN_N],tot;
void Eular_Griddle()//Linear Griddle
{
	int i,j;
	for(i=2;i<=n;i++)
	{
		if(!flag[i])prime[++tot]=i;
		for(j=1;j<=tot;j++)
		{
			if(i*prime[j]>n)break;
			flag[i*prime[j]]=true;
			if(i%prime[j]==0)break;
		}
	}
}

与平时我们写的筛法对比：

#define NN 100000
#define PRIME_IN_N 5000
bool flag[NN];
int prime[PRIME_IN_N],tot;
void Normal_Griddle()//O(NloglogN)
{
	int i,j;
	for(i=2;i<=n;i++)
	{
                if(flag[i])continue;
                prime[++tot]=i;
		for(j=i;j<=n/i;j++)
			flag[i*j]=true;
	}
}

基本上是一个意思。主要的区别在这里：if(i%prime[j]==0)break;

欧拉线性筛的效率保证在于每个数都只被筛中一次，而且是被它的最小质因数筛掉的（即n=i*prime[j]中的prime[j]是它的最小质因数）。曷故哉？

注意到prime[]是递增的，而且我们在第一次满足(i%prime[j]==0)时就break了，即此时的prime[j]是i的最小质因数（如果i是质数，那么就会把整个循环做完）。之前提到prime[j]必须为prime[j]*i的最小质因数才能保证效率。那么为了保证prime[j]*i的最小质因数是prime[j]，我们必须让prime[j]比i的最小质因数要小。这就是这一句话的含义。

这种线性筛比原来的筛法好了一些，效率提高，而且还能顺便求出每个数的最小质因数。这样就可以对一些积性函数求值了。

-----------------------------------------------------------------

pollard-rho。是一个寻找n的因子的方法。基于这个事实：如果a不为n的倍数，那么gcd(a,n)为n的一个因子。

I、选取一个x1

II、利用函数计算出x2使得x2-x1不被n整除。

III、如果gcd(x2-x1,n)>1那么找到因子，结束过程

IV、否则重复I。

----------------------------------------------------------------

觉得我的表达能力真是逆天了这些东西被我讲得好简单。看线性筛的时候蛋疼死我了。当然也可能是因为现在理解了所以看自己的解释觉得顺理成章- -。

惨惨惨。

总结写完了这下彻底没事情干了。