c++ - 在cpp中除以大数时查找大二进制字符串的余数

Question

我正在尝试解决hackerrank 上的“两个设置位”问题。问题链接：链接

基本上我有一个大的二进制字符串，并且想要除以这个余数：1000000007。

我正在使用 bitset 数据类型进行求解，当我将字符串转换为 long long int 时，to_ullong() 会导致溢出。

有没有办法摆弄字符串的一部分来获得剩余部分？

标签： c++stlc++14

Answer 1

当声明不公开时，很难回答你的问题。但是使用我的精神力量，我猜你的问题是如何知道任意长位序列模的余数K = 1000000007。

假设这确实是问题，您可以将您的位串记为：

b_0 b_1 ... b_n

其值为：

V = b_0*2^0 + b_1*2^1 + ... + b_n*2^n

鉴于您拥有的模运算的属性：

V % K = [ (b_0*2^0) % K + (b_1*2^1) % K + ... + (b_n*2^n) % K ] % K

对于低于 2 的幂，K计算很容易。对于其他人，您应该再次使用模属性：

V*W % K = [ (v % K) * (W % K) ] % K

例如：

2^(1000) % K = [ (2^10) % K * ... * (2^10) % K ] % K
               \_______________  __________________/
                               \/
                           100 factors

每个模数都很容易计算，而且比K使其适合long long.

总体复杂性将是O(n*log(n))，因为您执行O(log(n))操作来计算2^n % K，并且您执行此操作n。