代碼或Algo for Modulo Division

Question

我需要找到Res =（A/B）％P（P是素數）。

我有民= A％P和Den = B％P.

有隻需使用次數，書房和P任何方式找到RES？

(a/b) mod p = ((a mod p) * (b^(-1) mod p)) mod p 
i.e. Res = (Num * b^(p - 2) % p) % p 

現在，我怎麼二分找到B ^（P-2）使用書齋％P：

我碰到這個來的？

如果您可以提供給我一個C++/C代碼，我會非常高興，因爲我可以直接在我的遊戲中使用它，否則，請幫助我找到一個公式，以便我可以獲得Res我自己。

Answer 1

使用快速求冪可以得到b ^（p-2）％p的結果。

int qexp (int b, int e) { 
    if (e == 0) return 1; 
    long long h = qexp(b, e/2); //long long to prevent overflow in next step 
    h *= h; 
    h %= p; 
    if (e % 2 == 0) return h; 
    else return (h*b)%p; 
} 

使用qexp(b, p-2);