多模检验

问题

给你七个整数，计算是否成立

若给予数据范围过大，直接计算会超过数据范围，这时通常想到的是取模

• 若式子在某个模上不成立，则原式必定不成立（必要条件）
• 但如果两个数在一个模上同余，不能保证两个整数相等，因为两个不同整数也在同一模下同余

为了尽可能降低这种情况，我们需要用多个互质的大模数同时检验，选若干个大模数，要使得在这些模数上都为0，就必须被这些模的乘积整除，因此若我们选的模较大且个数够多，要求被他们整除的可能性就极小，可以有效避免上面的情况

解决方法

实际竞赛时，我们可以选择3-5个大素数进行测试，若都可以则通过检验

更保险的，我们可以使用64位usigned int自然溢出作为哈希取模，再加上一两个大模数

常见大素数选择

• 998244353:这是一个质数,它恰好是2的23次方加一,可以用来处理多项式的求逆、求 导、快速幂等操作。

• 1000000007:这也是一个质数,它恰好是1e9+7,经常用来解决组合数学、排 列组合等问题。

• 1000000009:与上一个配对，用于双模哈希

• 19260817:这也是一个质数,它是个比较大的质数,经常用来构造哈希表。

• 998244352:这是一个2的23次方,是一个比较小的2的幂次方,可以用来处理多项式的 快速幂、NTT等操作。

• 104857601:这是一个2的20次方加一,是一个比较小的2的幂次方,可以用来做NTT 等操作。