一些科技的总结

发表于 更新于 分类于

总结一些科技

主要收录比较神仙的，实用的算法技巧。

快速取模

原理

找到一个近似 \(m^{-1}\) 的形如 \(m'>>k\) 的数。

不妨就取 \(k=64,m'=\lceil\frac{2^{64}}{m}\rceil\)

然后 \(a\%b = a-a\times\lfloor\frac{a}{b}\rfloor = a-(a\times m'>>64)\)

纯纯的整数运算，经过误差分析，可以知道后式结果最多多减去一个 \(m\)，判断掉就行。

因为 \(a\) 常常是 \(\text{long long}\) 级别的数，所以开 __int128

优化据说有 \(5-6\) 倍，如果模数是 const，编译器会自动帮忙用这个优化。

代码

1
2
3
4
5
6
7
8
9
10
11
12
struct barrett{
	unsigned long long im;int m;
	barrett(unsigned m) :m(m), im(~0ull/m+1) {}
	int operator ()(int a,int b){
		unsigned long long z=(unsigned long long)a*b;
		int v=z-((__int128)z*im>>64)*m;
		return v<0?v+m:v;
	}
}bt(1);
  bt=barrett(p);
  c=bt(a,b);
//c=a*b%p

注意事项

  • 为啥 im,m 用 ull,uint，因为 m=2 时，会爆 long long。
  • 可以重载括号。

光速乘

用于计算两个 long long 级别的数乘积对一个 long long 级别的数取模的结果。

1
2
3
4
long long multi(long long a,long long b,long long mod){
	long long x=(unsigned long long)a*b-(unsigned long long)((long double)a*b/mod-0.5)*mod;
    return x>=mod?x-mod:x;
}
1
2
3
4
long long mul(long long A, long long B, long long P){
	long long C = A * B - (long long)((long double)A * B / P + 0.1) * P;
	return C < 0 ? C + P : C;
}

原理很简单，long double 的精度误差虽然有，但是我们 -0.5 之和核查范围变成了 [0,1]，肯定不会超出这个。

C++ 标准中要求了 unsigned long long 类型在溢出后保证为原值对 \(2^{64}\) 取模的结果，所以直接用就行。

第二个原理类似，在 G++ 编译器中，O2 中，保证 long long 的溢出行为有定义。

推荐用第一个，各个平台都不会出锅。

如果 \(P\leq 10^{14}\) 可以改成 double

判断一下是否减少了就行。