Модуль деления двух чисел

Question

Мы знаем это

(A + B) % P = (A % P + B % P) % P
(A * B) % P = (A % P * B % P) % P

где P это простое число.

Мне нужно рассчитать (A / B) % P где A,B может быть очень большим и может переполниться.

Имеет ли такая формула для модульной арифметики (A / B) % P а также (A - B) % P,

Если нет, то, пожалуйста, объясните, каков правильный ответ.

Т.е. это правда, что (A / B) % P = ((A % P) / (B % P)) % P?

Я пытался вычислить (N*(N^2+5)/6)%P, где N может достигать 10^15

здесь A=n*(n^2+5) может наверняка переполниться при n=10^15

Answer 1

Да, но это другое

(a - b) mod p = ((a mod p - b mod p) + p) mod p

(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

куда b^(-1) mod p является модульной инверсией b модификация p, За p = prime, b^(-1) mod p = b^(p - 2) mod p,

Редактировать:

(N * (N ^ 2 + 5) / 6)% Р

Вам не нужно никаких модульных инверсий из этого. Просто упростим дробь: N or N^2+5 будет делиться на 2 а также 3, Так что разделите их, и тогда у вас есть (a*b) mod P,

Answer 2

Влад отвечает правильно:

(a - b) mod p = ((a mod p - b mod p) + p) mod p
(a / b) mod p = ((a mod p) * (b^(-1) mod p)) mod p

Эти и некоторые другие операции описаны здесь в разделе Эквивалентности.

Просто хочу, чтобы вы знали, что это будет работать не только для простого числа p, Первый будет работать для любого p, Второй будет работать для любого p, где b^(-1) или модульное обратное определяется.

Модульное обратное вычисляется с помощью расширенного алгоритма Евклида.

Answer 3

Каким бы ни был ваш алгоритм, если входы A и B и если они переполнены, вы не сможете запустить алгоритм. Важно сказать нам, откуда эти цифры. Являются ли они суммой или произведением других ваших чисел?

Для больших чисел вы должны использовать специальную математическую библиотеку для больших чисел. Как обрабатывать произвольно большие целые числа С такими вероятностями библиотеки вы можете просто сделать (A/B)%P.

Answer 4

Ниже приводится еще один способ модульного деления двух чисел.

(A/B)%p = (A*modular_inverse(B))%p

      Also , 
int modular_inverse(int n, int p){
    return power(n, p-2, p);
}

int power(ll x, ll i,ll p)
{
int ans = 1;
while(i > 0){
    if(i&1)ans = (ans*x)%p;
     i >>=1;
     x = (x*x)%p;
   }
return ans;
}