Fermat's Little Theorem

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
using int64 = long long;
5
using i128 = __int128_t; // for safe multiplication when needed
6
7
// Fast modular exponentiation: computes a^e mod p in O(log e)
8
int64 mod_pow(int64 a, long long e, int64 p) {
9
    a %= p;
10
    if (a < 0) a += p;
11
    int64 res = 1 % p;
12
    while (e > 0) {
13
        if (e & 1LL) res = (int64)((i128)res * a % p);
14
        a = (int64)((i128)a * a % p);
15
        e >>= 1LL;
16
    }
17
    return res;
18
}
19
20
// Fermat inverse: valid only when p is prime and gcd(a, p) = 1
21
int64 mod_inv_fermat(int64 a, int64 p) {
22
    // Precondition checks are caller's responsibility in performance-critical code
23
    return mod_pow(a, p - 2, p);
24
}
25
26
int main() {
27
    ios::sync_with_stdio(false);
28
    cin.tie(nullptr);
29
30
    // Example: compute (a / b) mod p for multiple queries
31
    // Input format:
32
    // p q
33
    // then q lines of a b
34
    // Assumes p is prime and b not divisible by p
35
    long long p; int q;
36
    if (!(cin >> p >> q)) return 0;
37
38
    while (q--) {
39
        long long a, b; cin >> a >> b;
40
        a %= p; if (a < 0) a += p;
41
        b %= p; if (b < 0) b += p;
42
        if (b == 0) {
43
            cout << "Division undefined (b ≡ 0 mod p)\n";
44
            continue;
45
        }
46
        long long invb = mod_inv_fermat(b, p);
47
        long long ans = (long long)((i128)a * invb % p);
48
        cout << ans << '\n';
49
    }
50
    return 0;
51
}
52

1
#include <bits/stdc++.h>
2
using namespace std;
3
using int64 = long long;
4
using i128 = __int128_t;
5
6
int64 mod_pow(int64 a, long long e, int64 p) {
7
    a %= p; if (a < 0) a += p;
8
    int64 res = 1 % p;
9
    while (e > 0) {
10
        if (e & 1LL) res = (int64)((i128)res * a % p);
11
        a = (int64)((i128)a * a % p);
12
        e >>= 1LL;
13
    }
14
    return res;
15
}
16
17
struct Comb {
18
    int n;
19
    int64 p;
20
    vector<int64> fact, invfact;
21
    Comb(int n_, int64 p_) : n(n_), p(p_), fact(n_+1), invfact(n_+1) {
22
        fact[0] = 1;
23
        for (int i = 1; i <= n; ++i) fact[i] = (int64)((i128)fact[i-1] * i % p);
24
        // Compute invfact[n] = (fact[n])^{p-2} using Fermat
25
        invfact[n] = mod_pow(fact[n], p - 2, p);
26
        for (int i = n; i >= 1; --i) invfact[i-1] = (int64)((i128)invfact[i] * i % p);
27
    }
28
    int64 nCk(int n_, int k_) const {
29
        if (k_ < 0 || k_ > n_) return 0;
30
        return (int64)((i128)fact[n_] * invfact[k_] % p * invfact[n_-k_] % p);
31
    }
32
};
33
34
int main() {
35
    ios::sync_with_stdio(false);
36
    cin.tie(nullptr);
37
38
    // Example usage: precompute up to N and answer Q queries
39
    int N, Q; long long P;
40
    cin >> N >> P >> Q; // e.g., N=1000000, P=1000000007 (prime)
41
    Comb C(N, P);
42
43
    while (Q--) {
44
        int n, k; cin >> n >> k;
45
        cout << C.nCk(n, k) << '\n';
46
    }
47
    return 0;
48
}
49

1
#include <bits/stdc++.h>
2
using namespace std;
3
using int64 = long long;
4
using i128 = __int128_t;
5
6
int64 mod_pow(int64 a, long long e, int64 m) {
7
    a %= m; if (a < 0) a += m;
8
    int64 res = 1 % m;
9
    while (e > 0) {
10
        if (e & 1LL) res = (int64)((i128)res * a % m);
11
        a = (int64)((i128)a * a % m);
12
        e >>= 1LL;
13
    }
14
    return res;
15
}
16
17
bool is_fermat_probable_prime(long long n, int iterations = 10) {
18
    if (n < 2) return false;
19
    // Small primes check
20
    for (long long p : {2LL, 3LL, 5LL, 7LL, 11LL, 13LL, 17LL, 19LL, 23LL, 29LL, 31LL, 37LL}) {
21
        if (n == p) return true;
22
        if (n % p == 0) return false;
23
    }
24
    std::mt19937_64 rng(1234567);
25
    std::uniform_int_distribution<long long> dist(2, n - 2);
26
    for (int i = 0; i < iterations; ++i) {
27
        long long a = dist(rng);
28
        if (std::gcd(a, n) != 1) return false; // found a nontrivial gcd => composite
29
        if (mod_pow(a, n - 1, n) != 1) return false; // violates FLT => composite
30
    }
31
    return true; // probable prime (can be wrong for Carmichael numbers)
32
}
33
34
int main() {
35
    ios::sync_with_stdio(false);
36
    cin.tie(nullptr);
37
38
    long long n; cin >> n;
39
    bool probable = is_fermat_probable_prime(n, 20);
40
    cout << (probable ? "probable prime (Fermat)" : "composite") << "\n";
41
    return 0;
42
}
43

1
#include <bits/stdc++.h>
2
using namespace std;
3
using int64 = long long;
4
using i128 = __int128_t;
5
6
int64 mod_pow(int64 a, long long e, int64 p) {
7
    a %= p; if (a < 0) a += p;
8
    int64 res = 1 % p;
9
    while (e > 0) {
10
        if (e & 1LL) res = (int64)((i128)res * a % p);
11
        a = (int64)((i128)a * a % p);
12
        e >>= 1LL;
13
    }
14
    return res;
15
}
16
17
int main() {
18
    ios::sync_with_stdio(false);
19
    cin.tie(nullptr);
20
21
    long long a, p; string b;
22
    // Input: a p b (with p prime, b is nonnegative integer as decimal string)
23
    if (!(cin >> a >> p >> b)) return 0;
24
25
    a %= p; if (a < 0) a += p;
26
27
    if (b == "0") {
28
        // a^0 mod p = 1 for any a != 0; 0^0 is undefined but often treated as 1 in programming contests
29
        cout << 1 % p << "\n";
30
        return 0;
31
    }
32
33
    if (a == 0) {
34
        // 0^b mod p is 0 for b > 0
35
        cout << 0 << "\n";
36
        return 0;
37
    }
38
39
    // Reduce exponent modulo (p-1) using FLT because gcd(a, p) = 1
40
    long long phi = p - 1; // since p is prime
41
    long long e_mod = 0;
42
    for (char c : b) {
43
        int d = c - '0';
44
        e_mod = ( ( (__int128)e_mod * 10 ) + d ) % phi;
45
    }
46
47
    cout << mod_pow(a, e_mod, p) << "\n";
48
    return 0;
49
}
50