模算子与除法算子

Question

两个数字A和B给了我们。

给出了A完全可以被B整除的结论。

我需要计算(A/B)%MOD.

我们只知道两件事，A%MOD, B。我们如何从以上两件事中计算出这一点。

实问题

num = (1*2*3.....*262143)%MOD，我们都知道。

现在，我的任务是计算(2*3*4*...*262144)%MOD，然后计算(3*4*5*....*262145)%MOD，以此类推。

在哪里，MOD = 1000000009。

更新:-

A = (2*3*4)%7 = ( 2%7 * 3%7 * 4%7)%7 = 3
B = ( (A*(5%7))%7 )/(2%7) = 0 .......................**THAT IS WRONG, ANSWER SHOULD BE 4**

Answer 1

由于1000000009是素数，所以问题很容易解决。您需要使用模乘逆。

(A / B) % MOD = ((A % MOD) * (B^-1 % MOD)) % MOD

您可以为此使用费马小定理，也就是说，如果p是素数，那么

a^(p - 1) % p = 1, 

这导致了

(a * a^(p - 2)) % p = 1, 

含义

a^(p - 2)

是a mod p的模逆。

A = (2 * 3 * 4 * ... * 262144) % MOD
B = (3 * 4 * 5 * ... * 262145) % MOD
  = (A * (2^1000000007 % MOD) * (262145 % MOD)) % MOD

Answer 2

(x * y) % mod = (x % mod) * (y % mod)

考虑到这个身份，您可以很容易地找到答案：

A= (1 *2*3.*262143)%MOD=(1% MOD *2% MOD *3.*262143% MOD) B= (2 *3.*262144)%MOD=(2% MOD *3.*262144% MOD) B=A* (262144 % MOD) = (A * 262144) % MOD。