Find (num * (pow(b, p) - 1) / den) % mod where p is very large(10 ^ 18)

Question

我想找到 (num * (pow(b, p) - 1) / den) % mod。我知道二进制求幂。但我们不能直截了当地做到这一点。保证分子可以被分母整除。这意味着

[num * (pow(b, p) - 1)] % den == 0

对 mod 的约束：1 <= mod <= 10 ^ 9 并且 mod 可能是质数或合数

对 b 的约束：1 <= b <= 10

对 p 的约束：1 <= p <= (10^18)

对 num 的限制：1 <= num <= (10^9)

den 的约束：1 <= den <= (10^9)

这里的 pow(b, p) 表示 b 的幂 p(b ^ p)。保证分子可以被分母整除。我怎样才能用二进制求幂

Answer 1

您的表达式应该重写以简化它。首先让k=num/den，k根据你的问题整数。

所以你必须计算
(k×(b^p-1))mod m=( (k mod m) × ((b^p -1) mod m) ) mod米
= ( (k mod m) × ( (b^p mod m) -1 mod m ) mod m ) mod m
= ((k mod m) × ((b^p mod m) + m-1) mod m) mod m (1)

所以真正的问题是计算 b^p mod m

许多语言（python、java 等）在其标准库中已经有 mod 元求幂。查阅文档并使用它。否则，这里是 C 实现。

unsigned long long modexp(unsigned long long b, unsigned long long e, unsigned long long m) {
  if (m==1) return 0;
  unsigned long long res=1;
  unsigned long long bb = b % m;
  while (e) {
    if (e & 1) 
      res = (res*b) % m;
    e >>= 1;
    bb = (bb*bb) % m;
  }
  return res;
}

实施使用 long long 来满足您的限制。它依赖于二进制取幂的经典技巧。 b^l 的所有值，其中 l 是 2 的幂 (l=2^t) 被计算并存储在 var bb 中，如果 e 的相应 t^th 位被设置， b^l 的这个值集成在结果中。位测试通过检查 e 的连续奇偶校验来完成，同时在每一步向右移动 e。

最后，(a×b)mod m=((a mod m)×(b mod m))mod m 是用于避免对非常大的数字进行计算。我们总是有 res

那么您只需应用(1)即可得到最终结果。

根据评论中给出的精度进行编辑
要计算 n=(3^p-1)/2 mod m，可以注意到
(3^p-1)/2 = x*m + n（因为3^p-1是偶数，x是整数，0≤n 3^p-1=x*2*m+2n (0≤2n<2m)
所以 2n=(3^p-1) mod 2m

我们可以只应用前面的方法，modulo 为 2*m，并将结果（这将是偶数）除以 2。

Find (num * (pow(b, p) - 1) / den) % mod where p is very large(10 ^ 18)

Find (num * (pow(b, p) - 1) / den) % mod where p is very large(10 ^ 18)

binary

exponentiation