Соревнования по кодированию: как хранить большие числа и находить все их модульные модули P

Что касается большого количества библиотек, я использовал ttmath, который предоставляет произвольные целые числа длины, числа с плавающей запятой и т. д., и некоторые действительно хорошие операции, причем с относительно небольшим объемом.

Однако, если вы только пытаетесь выяснить, что такое (n ^ e) mod m, вы можете сделать это для очень больших значений e даже без вычисления очень большого числа. Ниже приведена функция, которую я добавил в свою локальную библиотеку ttmath, чтобы сделать именно это:

/*!
mod power this = (this ^ pow) % m
binary algorithm (r-to-l)

return values:
0 - ok
1 - carry
2 - incorrect argument (0^0)
*/
uint PowMod(UInt<value_size> pow, UInt<value_size> mod)
{
if(pow.IsZero() && IsZero())
// we don't define zero^zero
return 2;

UInt<value_size> remainder;
UInt<value_size> x = 1;

uint c = 0;

while (pow != 0)
{
remainder = (pow & 1 == 1);
pow /= 2;
if (remainder != 0)
{
c += x.Mul(*this);
x = x % mod;
}

c += Mul(*this);
*this = *this % mod;
}

*this = x;
return (c==0)? 0 : 1;
}

Я не думаю, что вам когда-либо нужно хранить число больше, чем n ^ 2 для этого алгоритма. Это должно быть легко изменить так, чтобы убрать связанные с ttmath аспекты, если вы не хотите использовать эти заголовки.

Вы можете найти детали математики онлайн, посмотрев вверх модульное возведение в степень, если ты заботишься об этом.

Если нам нужно вычислить nCr mod p (где p — простое число), мы можем вычислить факториальный mod p, а затем использовать модульное обратное, чтобы найти nCr mod p. Если нам нужно найти nCr mod m (где m не простое число), мы можем разложить m на простые числа, а затем использовать теорему об остатках в Китае (CRT), чтобы найти nCr mod m.

#include<iostream>
using namespace std;
#include<vector>

/* This function calculates (a^b)%MOD */
long long pow(int a, int b, int MOD)
{
long long x=1,y=a;
while(b > 0)
{
if(b%2 == 1)
{
x=(x*y);
if(x>MOD) x%=MOD;
}
y = (y*y);
if(y>MOD) y%=MOD;
b /= 2;
}
return x;
}

/*  Modular Multiplicative Inverse
Using Euler's Theorem
a^(phi(m)) = 1 (mod m)
a^(-1) = a^(m-2) (mod m) */
long long InverseEuler(int n, int MOD)
{
return pow(n,MOD-2,MOD);
}

long long C(int n, int r, int MOD)
{
vector<long long> f(n + 1,1);
for (int i=2; i<=n;i++)
f[i]= (f[i-1]*i) % MOD;
return (f[n]*((InverseEuler(f[r], MOD) * InverseEuler(f[n-r], MOD)) % MOD)) % MOD;
}

int main()
{
int n,r,p;
while (~scanf("%d%d%d",&n,&r,&p))
{
printf("%lld\n",C(n,r,p));
}
}

Здесь я использовал long long int, чтобы записать число.

Во многих. во многих случаях в этих соревнованиях по кодированию идея заключается в том, что вы на самом деле не рассчитываете эти большие числа, а выясняете, как ответить на вопрос, не вычисляя его. Например:

What are the last ten digits of 1,000,000! (factorial)?

Это число с более чем пятью миллионами цифр. Однако я могу ответить на этот вопрос без компьютера, даже не используя ручку и бумагу. Или возьмите вопрос: что такое (2014 ^ 2014) по модулю 153? Вот простой способ рассчитать это в C:

int modulo = 1;
for (int i = 0; i < 2014; ++i) modulo = (modulo * 2014) % 153;

Опять же, вы избежали делать вычисления с 6000-значным числом. (Вы можете сделать это значительно быстрее, но я не пытаюсь участвовать в конкурсе).