- Number Theory
1.1 Chinese Remainder Theorem
Problem Statement
Given a system of congruences:
\[ \begin{cases} x \equiv a_1 \pmod{b_1} \\ x \equiv a_2 \pmod{b_2} \\ \vdots \\ x \equiv a_n \pmod{b_n} \end{cases} \]
Find the smallest positive integer solution for \(x\), where \(b_i\) (for \(i \in [1,n]\)) are pairwise coprime.
Theoretical Analysis
If a solution exists, it will be unique modulo \(M = \operatorname{lcm}(b_1, b_2, \dots, b_n)\).
Let \(M = b_1b_2\dots b_n\) and \(m_i = \frac{M}{b_i}\).
Since \(b_j \mid m_i\) and \(\gcd(m_i, b_i) = 1\) for \(i \in [1,n]\) and \(j \in [1,n]\) with \(j \ne i\), by Bézout's identity, there exist integers \(u_i, v_i\) such that:
\[u_im_i + v_ib_i = 1\]
The solution is given by:
\[x \equiv \sum_{i=1}^n u_i a_i m_i \pmod{M}\]
Implementation
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
typedef long long ll;
const int MAX_EQUATIONS = 20;
ll equationCount, solution, modulusProduct = 1;
ll remainders[MAX_EQUATIONS], moduli[MAX_EQUATIONS];
ll partialModuli[MAX_EQUATIONS], coefficients[MAX_EQUATIONS], inverses[MAX_EQUATIONS];
ll readInt() {
ll value = 0, sign = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') sign = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
value = value * 10 + (ch - '0');
return value * sign;
}
void extendedGCD(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1, y = 0;
return;
}
extendedGCD(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - (a / b) * y;
}
int main() {
equationCount = readInt();
for (ll i = 0; i < equationCount; ++i) {
moduli[i] = readInt();
remainders[i] = readInt();
modulusProduct *= moduli[i];
}
for (ll i = 0; i < equationCount; ++i)
partialModuli[i] = modulusProduct / moduli[i];
for (ll i = 0; i < equationCount; ++i)
extendedGCD(partialModuli[i], moduli[i], coefficients[i], inverses[i]);
for (ll i = 0; i < equationCount; ++i)
solution = (solution + coefficients[i] * remainders[i] * partialModuli[i] % modulusProduct) % modulusProduct;
printf("%lld\n", (solution + modulusProduct) % modulusProduct);
return 0;
}
1.2 Extended Chinese Remainder Theorem
Problem Statement
Given the same system of congruences as above, but without the requirement that the moduli \(b_i\) are pairwise coprime.
Theoretical Analysis
Consider the first two equations:
\[ \begin{cases} x \equiv a_1 \pmod{b_1} \\ x \equiv a_2 \pmod{b_2} \end{cases} \]
We can rewrite these as:
\[ \begin{cases} x = a_1 + u \cdot b_1 \\ x = a_2 + v \cdot b_2 \end{cases} \]
This leads to: \(a_1 + u \cdot b_1 = a_2 + v \cdot b_2\), or \(b_1 \cdot u - b_2 \cdot v = a_2 - a_1\).
This equation has a solution if and only if \(\gcd(b_1, b_2) \mid (a_2 - a_1)\). If a solution exists, we can find values for \(u\) and \(v\), and thus determine \(x\).
We then merge these two equations into one and continue with the next equation, repeating the process until all equations are resolved.
Implementation
#include <iostream>
using namespace std;
typedef long long ll;
ll equationCount, currentRemainder, currentModulus, solution, lcmValue;
bool noSolution = false;
ll readInt() {
ll value = 0, sign = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') sign = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
value = value * 10 + (ch - '0');
return value * sign;
}
ll safeMultiply(ll a, ll b, ll mod, ll result = 0) {
for (; b; b >>= 1, a = (a << 1) % mod)
if (b & 1) result = (result + a) % mod;
return result;
}
ll extendedGCD(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll gcd = extendedGCD(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - (a / b) * y;
return gcd;
}
int main() {
equationCount = readInt();
currentModulus = readInt();
currentRemainder = readInt();
lcmValue = currentModulus;
solution = currentRemainder;
for (ll i = 1; i < equationCount; ++i) {
ll nextModulus = readInt();
ll nextRemainder = (readInt() - solution % nextModulus + nextModulus) % nextModulus;
ll coefficient1, coefficient2;
ll gcd = extendedGCD(lcmValue, nextModulus, coefficient1, coefficient2);
if (nextRemainder % gcd != 0) {
noSolution = true;
} else {
ll multiplier = safeMultiply(coefficient1, nextRemainder / gcd, nextModulus);
solution += multiplier * lcmValue;
lcmValue = lcmValue / gcd * nextModulus;
solution = (solution % lcmValue + lcmValue) % lcmValue;
}
}
if (noSolution) {
puts("-1");
} else {
printf("%lld\n", solution);
}
return 0;
}
1.3 Baby-Step Giant-Step Algorithm
Problem Statement
Given positive integers \(a, b, p\) with \(\gcd(a, p) = 1\), find the smallset non-negative integer \(x\) such that \(a^x \equiv b \pmod{p}\).
Theoretical Analysis
Since \(\gcd(a, p) = 1\), we can perform arithmetic operations with \(a\) modulo \(p\).
Let \(x = i \cdot t - j\) where \(t = \lceil\sqrt{p}\rceil\) and \(j \in [0, t)\).
Then \(a^{i \cdot t - j} \equiv b \pmod{p}\) can be rewritten as \((a^t)^i \equiv b \cdot a^j \pmod{p}\).
We can store all values of \(b \cdot a^j\) in a hash table and then check for values of \((a^t)^i\) to find a match.
Implementation
#include <iostream>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
ll base, target, modulus, result;
ll modularExponentiation(ll base, ll exponent, ll mod, ll result = 1) {
for (; exponent; exponent >>= 1, base = base * base % mod)
if (exponent & 1) result = result * base % mod;
return result % mod;
}
ll babyStepGiantStep(ll a, ll b, ll p) {
map<ll, ll> valueMap;
valueMap.clear();
b %= p;
ll stepSize = (ll)sqrt(p) + 1;
// Baby steps: compute and store b * a^j for all j in [0, stepSize)
for (ll j = 0, val; j < stepSize; ++j) {
val = b * modularExponentiation(a, j, p) % p;
valueMap[val] = j;
}
// Giant steps: compute a^(stepSize) and check for matches
a = modularExponentiation(a, stepSize, p);
if (a == 0) return b == 0 ? 1 : -1;
for (ll i = 0, j, val; i <= stepSize; ++i) {
val = modularExponentiation(a, i, p);
auto it = valueMap.find(val);
j = (it == valueMap.end()) ? -1 : it->second;
if (j >= 0 && i * stepSize - j >= 0) {
return i * stepSize - j;
}
}
return -1;
}
int main() {
scanf("%lld %lld %lld", &base, &target, &modulus);
result = babyStepGiantStep(base, target, modulus);
if (result != -1) {
printf("%lld\n", result);
} else {
puts("no solution");
}
return 0;
}
1.4 Example Problem: Calculator
Problem Statement
Given \(n\) queries and a query type \(op\), each query provides integers \(a, b, p\):
- If \(op = 1\), compute \(a^b \bmod p\)
- If \(op = 2\), find the smallest non-negative integer \(x\) such that \(a \cdot x \equiv b \pmod{p}\)
- If \(op = 3\), find the smallest non-negative integer \(x\) such that \(a^x \equiv b \pmod{p}\)
Theoretical Analysis
- For \(op = 1\), use fast exponentiation
- For \(op = 2\), use the extended Euclidean algorithm
- For \(op = 3\), use the BSGS algorithm
Implementation
#include <iostream>
#include <map>
#include <cmath>
using namespace std;
typedef long long ll;
ll num1, num2, modulus;
ll readInt() {
ll value = 0, sign = 1;
char ch = getchar();
for (; ch < '0' || ch > '9'; ch = getchar())
if (ch == '-') sign = -1;
for (; ch >= '0' && ch <= '9'; ch = getchar())
value = value * 10 + (ch - '0');
return value * sign;
}
ll fastExponentiation(ll base, ll exponent, ll result = 1) {
for (; exponent; exponent >>= 1, base = base * base % modulus)
if (exponent & 1) result = result * base % modulus;
return result % modulus;
}
ll extendedGCD(ll a, ll b, ll& x, ll& y) {
if (b == 0) {
x = 1, y = 0;
return a;
}
ll gcd = extendedGCD(b, a % b, x, y);
ll temp = x;
x = y;
y = temp - (a / b) * y;
return gcd;
}
ll discreteLogarithm(ll a, ll b, ll p) {
map<ll, ll> valueMap;
valueMap.clear();
b %= p;
ll stepSize = (ll)sqrt(p) + 1;
for (ll j = 0, val; j < stepSize; ++j) {
val = b * fastExponentiation(a, j) % p;
valueMap[val] = j;
}
a = fastExponentiation(a, stepSize);
if (a == 0) return b == 0 ? 1 : -1;
for (ll i = 0, j, val; i <= stepSize; ++i) {
val = fastExponentiation(a, i);
auto it = valueMap.find(val);
j = (it == valueMap.end()) ? -1 : it->second;
if (j >= 0 && i * stepSize - j >= 0) {
return i * stepSize - j;
}
}
return -1;
}
int main() {
ll queryCount = readInt();
ll operationType = readInt();
while (queryCount--) {
num1 = readInt();
num2 = readInt();
modulus = readInt();
if (operationType == 1) {
printf("%lld\n", fastExponentiation(num1, num2));
}
else if (operationType == 2) {
ll x, y;
ll gcd = extendedGCD(num1, modulus, x, y);
while (x < 0) x += modulus;
if (num2 % gcd != 0) {
puts("Orz, I cannot find x!");
} else {
printf("%lld\n", x * num2 / gcd % modulus);
}
}
else {
ll ans = discreteLogarithm(num1, num2, modulus);
if (ans == -1) {
puts("Orz, I cannot find x!");
} else {
printf("%lld\n", ans);
}
}
}
return 0;
}
- Combinatorics
2.1 Lucas Theorem
Problem Statement
Given positive integers \(n, m, p\) where \(p\) is prime, compute \(C_{n+m}^n \bmod p\).
Theoretical Analysis
Lucas' theorem states that for non-negative integers \(m, n\) and prime \(p\), the following congruence relation holds:
\[C_n^m \equiv \prod_{i=0}^{k} C_{n_i}^{m_i} \pmod{p}\]
where \(n_i\) and \(m_i\) are the digits of \(n\) and \(m\) in base \(p\).
2.2 Extended Lucas Theorem
Problem Statement
Given positive integers \(n, m, p\), compute \(C_n^m \bmod p\) where \(p\) is not necessarily prime.
Theoretical Analysis
The extended Lucas theorem allows computation of binomial coefficients modulo composite numbers by factorizing the modulus and applying the Chinese Remainder Theorem.