知识杂项

大数翻倍法

用于解决线性同余方程组（中国剩余定理）的一种优化暴力，好写好记，而且正确率较高。

暴力做法：对于其中两个同余方程进行合并

wihle (a1%n2!=a2) a1+=n1;
return (a1, lcm(n1,n2));

复杂度好像是一种 \(\sum n_i-\max n_i\) (\(n_i\) 为模数) 的奇怪的东西。

具体做法是将暴力的做法优化了些。

inline node merge(node a, node b)
{
	if (a.m < b.m) swap(a, b);
	//唯一的优化
	while (a.a%b.m != b.a)
		a.a += a.m;
	
	a.m = lcm(a.m, b.m);
	return a;
}

后话：洛谷的CRT模板题，虽然暴力也能水过。但这三者之间的速度差异依然可以由P4777 【模板】扩展中国剩余定理（EXCRT）看出。

More