Stanislav Volodarskiy немного слукавил, когда сказал, что делить по модулю нельзя. На самом деле деление по модулю вполне определено для делителей взаимно простых с самим модулем как умножение на обратный к делителю элемент в кольце.
Для того чтобы разделить N
на 7
по модулю 20
, если N % 20 = 5
(например, N = 105
), нужно найти 7^(-1) = 3 (mod 20)
и просто вычислить ((N % mod) * D^(-1)) % mod
, что при подстановке тождественно (5 * 3) % 20 = 15
. Проверим результат реальным делением 105
на 7
: 105 / 7 = 15
, 15 % 20 = 15
. Таким образом, мы действительно "разделили" остаток R
на некоторое число D
и получили новый остаток R'
, причем это произошло корректно для каждого числа в кольце, соответствующего данному остатку R
, которое делится на D
.
При этом, можно утверждать, что делить на не взаимно простые делители нельзя, так как результат либо не будет существовать, либо будет не единственным. Доказывать это, как и свой прошлый абзац я не буду, послушайте какой-нибудь нормальный курс модульной арифметики, если хотите подробностей.
Таким образом, мы можем делить заданное остатком число на любое взаимно простое с модулем. Чтобы делить заданное остатком число вообще на любое, просто будем хранить степени простых, входящих в разложение модуля, вдобавок к его остатку (точнее к особому остатку).
Если конкретно, то давайте представим наше число N
как (A^a * B^b * ... * D^d) * R
, где A, B, ..., D
- простые, входящие в разложение модуля, а R
- произведение всех остальных степеней простых. Тогда остаток от N
мы можем вычислить просто перемножив остатки степеней A^a, B^b, ... D^d
между собой и с остатком от R
. Получается, что поддерживая степени a, b, ..., d
и остаток от произведения R
, мы можем в любой момент получить остаток от текущего значения N
. Очевидно, что можно поддерживать степени при умножении и делении и R
при умножении. Но так как R
мы будем делить только на некоторое D
, в разложение которого не входят простые из разложения M
, то D
- взаимно просто с модулем, а значит, для деления мы можем просто умножить R
на обратное к D
, что не составляет никаких проблем.
То есть число 105
по модулю 20
мы представили бы как [{2: 0, 5: 1}, (105 / (2^0 * 5^1)) % 20]
. Таким образом, при делении на 15
, мы можем сначала разделить наше число N = 105
разделить на 5
, которое входит в разложение модуля, а потом разделить остаток на 3
, которое уже взаимно просто с модулем. Тогда мы получаем число [{2: 0, 5: 1 - 1}, (1 * 3^(-1)) % 20] = 7 (mod 20)
.
Если использовать данный способ, то в общем случае асимптотики операций при их оптимальной реализации такие:
Init(N, M)
: Инициализация объекта числом N
по модулю M
: O(sqrt(M) + Mult(N))
.
Mult(N)
: Умножение рассматриваемого числа на N
по рассматриваемому модулю M
: O(log(N) + log(M))
Div(N)
: Деление рассматриваемого числа на N
по рассматриваемому модулю M
: O(log(N) + log(M))
Get()
: Получение остатка рассматриваемого числа по рассматриваемому модулю M
после K
операций умножения: O(log(M) * log(K))
или около того
Так как существует формула C(n) = C(n - 1) * (4n - 2) / (n + 1)
, то общая сложность алгоритма составит O(N * (log(N) + log(M)) + sqrt(M))
, если ничего не путаю
Код:
#include "iostream"
#include "vector"
#include "algorithm"
#define ll long long
using namespace std;
struct Number
{
int M;
vector<int> M_factors;
vector<int> M_degrees;
vector<int> X_degrees;
ll remainder;
int phi;
void factor(int n, vector<int>& factors, vector<int>& degrees)
{
int x = n;
for (int i = 2; i * i <= n; i++)
{
if (x % i == 0)
{
factors.push_back(i);
degrees.push_back(0);
while (x % i == 0)
{
degrees[degrees.size() - 1]++;
x /= i;
}
}
}
if (x > 1)
{
factors.push_back(x);
degrees.push_back(1);
}
}
int phi_function(vector<int>& factors, vector<int>& degrees)
{
int res = 1;
for (int i = 0; i < factors.size(); i++)
{
int z = 1;
for (int j = 0; j < degrees[i]; j++)
z *= factors[i];
res *= z - z / factors[i];
}
return res;
}
int reverse_element(ll x)
{
ll res = 1, pow = phi - 1;
while (pow) //101
{
if (pow & 1)
res = (res * x) % M;
x = (x * x) % M;
pow >>= 1;
}
return res;
}
Number(int mod)
{
M = mod;
factor(mod, M_factors, M_degrees);
X_degrees = vector<int>(M_factors.size(), 0);
remainder = 1;
phi = phi_function(M_factors, M_degrees);
}
Number operator *=(int x)
{
for (int i = 0; i < M_factors.size(); i++)
{
while (x % M_factors[i] == 0)
{
X_degrees[i]++;
x /= M_factors[i];
}
}
remainder = (remainder * x) % M;
return *this;
}
Number operator /=(int x)
{
for (int i = 0; i < M_factors.size(); i++)
{
while (x % M_factors[i] == 0)
{
X_degrees[i]--;
x /= M_factors[i];
}
}
remainder = (remainder * reverse_element(x)) % M;
return *this;
}
// Как оказалось, в итоге я не могу оптимизировать get() так, как изначально предполагал.
// В моей реализации его асимптотика составляет O(N*log(N)), где N - количество выполненных умножений
// Однако используя бинарное возведение в степень можно улучшить до O(log(M) * log(N)), где N - количество выполненных умножений
int get()
{
ll res = remainder;
for (int i = 0; i < M_factors.size(); i++)
for (int j = 0; j < X_degrees[i]; j++)
res = (res * M_factors[i]) % M;
return res;
}
};
int main()
{
int n, m;
cin >> n >> m;
Number x(m);
for (int i = 1; i <= n; i++)
{
x *= 4 * i - 2;
x /= i + 1;
}
cout << x.get() << '\n';
return 0;
}
Спасибо Станиславу за проверку и измерение скорости работы программы: n=10000, m=1000000000 -> 0.010s