Euler's Totient Function

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Computes Euler's Totient phi(n) by trial division.
5
// Works well for single n up to about 1e12 in typical time limits.
6
long long phi_trial_division(long long n) {
7
    if (n == 0) return 0; // conventionally undefined, but return 0 here
8
    long long result = n; // start with n and apply multiplicative updates
9
    // Handle factor 2 separately for small optimization
10
    if ((n & 1LL) == 0) {
11
        result = result / 2; // multiply by (1 - 1/2)
12
        while ((n & 1LL) == 0) n >>= 1; // remove all factors of 2
13
    }
14
    // Try odd factors up to sqrt(n)
15
    for (long long p = 3; p * p <= n; p += 2) {
16
        if (n % p == 0) {
17
            result = result / p * (p - 1); // multiply by (1 - 1/p)
18
            while (n % p == 0) n /= p;     // remove all factors of p
19
        }
20
    }
21
    // If n > 1 now, it's a prime factor larger than sqrt(original n)
22
    if (n > 1) {
23
        result = result / n * (n - 1);
24
    }
25
    return result;
26
}
27
28
int main() {
29
    ios::sync_with_stdio(false);
30
    cin.tie(nullptr);
31
32
    long long n;
33
    if (!(cin >> n)) return 0;
34
    cout << phi_trial_division(n) << "\n";
35
    return 0;
36
}
37

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Linear (Euler) sieve to compute phi[1..N] in O(N) time.
5
// Also computes the Farey sequence length |F_N| = 1 + sum_{k=1}^N phi(k).
6
7
int main() {
8
    ios::sync_with_stdio(false);
9
    cin.tie(nullptr);
10
11
    int N; // e.g., up to 1e7 depending on memory/time limits
12
    if (!(cin >> N)) return 0;
13
14
    vector<int> phi(N + 1);
15
    vector<int> primes;
16
    vector<bool> is_composite(N + 1, false);
17
18
    phi[0] = 0;
19
    if (N >= 1) phi[1] = 1;
20
21
    for (int i = 2; i <= N; ++i) {
22
        if (!is_composite[i]) {
23
            primes.push_back(i);
24
            phi[i] = i - 1; // phi(p) = p - 1 for prime p
25
        }
26
        for (int p : primes) {
27
            long long v = 1LL * i * p;
28
            if (v > N) break;
29
            is_composite[(int)v] = true;
30
            if (i % p == 0) {
31
                // p divides i: phi(i * p) = phi(i) * p
32
                phi[(int)v] = phi[i] * p;
33
                break; // crucial for linear complexity
34
            } else {
35
                // p does not divide i: phi(i * p) = phi(i) * (p - 1)
36
                phi[(int)v] = phi[i] * (p - 1);
37
            }
38
        }
39
    }
40
41
    // Compute Farey sequence length |F_N| = 1 + sum_{k=1}^N phi(k)
42
    long long farey_len = 1; // starts with 1
43
    for (int k = 1; k <= N; ++k) farey_len += phi[k];
44
45
    // Output a few sample values and the Farey length
46
    cout << "phi(1..min(N,10)): ";
47
    for (int i = 1; i <= min(N, 10); ++i) cout << phi[i] << (i == min(N, 10) ? '\n' : ' ');
48
    cout << "|F_" << N << "| = " << farey_len << "\n";
49
    return 0;
50
}
51

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
// Precompute SPF (smallest prime factor) up to MAXV and answer Q totient queries.
5
// For each query n, reconstruct its distinct prime factors using SPF and apply
6
// phi(n) = n * product_{p | n} (1 - 1/p).
7
8
struct SPF {
9
    int MAXV;
10
    vector<int> spf; // smallest prime factor for each x
11
    explicit SPF(int maxv): MAXV(maxv), spf(maxv + 1) {
12
        build();
13
    }
14
    void build() {
15
        iota(spf.begin(), spf.end(), 0);
16
        for (int i = 2; 1LL * i * i <= MAXV; ++i) {
17
            if (spf[i] == i) { // i is prime
18
                for (long long j = 1LL * i * i; j <= MAXV; j += i) {
19
                    if (spf[(int)j] == (int)j) spf[(int)j] = i;
20
                }
21
            }
22
        }
23
    }
24
    // Factorization returning distinct primes dividing n
25
    vector<int> distinct_primes(int n) const {
26
        vector<int> ps;
27
        while (n > 1) {
28
            int p = spf[n];
29
            ps.push_back(p);
30
            while (n % p == 0) n /= p;
31
        }
32
        return ps;
33
    }
34
};
35
36
long long phi_from_distinct_primes(long long n, const vector<int>& primes) {
37
    long long res = n;
38
    for (int p : primes) {
39
        res = (res / p) * (p - 1);
40
    }
41
    return res;
42
}
43
44
int main() {
45
    ios::sync_with_stdio(false);
46
    cin.tie(nullptr);
47
48
    int MAXV, Q;
49
    if (!(cin >> MAXV >> Q)) return 0;
50
    SPF spf(MAXV);
51
52
    while (Q--) {
53
        int n; cin >> n;
54
        if (n == 0) { cout << 0 << '\n'; continue; }
55
        if (n == 1) { cout << 1 << '\n'; continue; }
56
        auto ps = spf.distinct_primes(n);
57
        cout << phi_from_distinct_primes(n, ps) << '\n';
58
    }
59
    return 0;
60
}
61

1
#include <bits/stdc++.h>
2
using namespace std;
3
4
long long phi_trial_division(long long n) {
5
    if (n == 0) return 0;
6
    long long result = n;
7
    if ((n & 1LL) == 0) {
8
        result = result / 2;
9
        while ((n & 1LL) == 0) n >>= 1;
10
    }
11
    for (long long p = 3; p * p <= n; p += 2) {
12
        if (n % p == 0) {
13
            result = result / p * (p - 1);
14
            while (n % p == 0) n /= p;
15
        }
16
    }
17
    if (n > 1) result = result / n * (n - 1);
18
    return result;
19
}
20
21
long long mod_mul(long long a, long long b, long long m) {
22
    // Safe multiplication for 64-bit using __int128
23
    __int128 r = ( __int128)a * b % m;
24
    return (long long)r;
25
}
26
27
long long mod_pow(long long a, long long e, long long m) {
28
    long long r = 1 % m;
29
    a %= m;
30
    while (e > 0) {
31
        if (e & 1) r = mod_mul(r, a, m);
32
        a = mod_mul(a, a, m);
33
        e >>= 1;
34
    }
35
    return r;
36
}
37
38
// Returns modular inverse of a modulo m if gcd(a,m)=1; otherwise returns -1.
39
long long mod_inverse_totient(long long a, long long m) {
40
    long long g = std::gcd(a, m);
41
    if (g != 1) return -1; // inverse does not exist
42
    long long ph = phi_trial_division(m);
43
    // Euler: a^{phi(m)} ≡ 1 (mod m) => a^{phi(m)-1} is the inverse
44
    return mod_pow((a % m + m) % m, ph - 1, m);
45
}
46
47
int main() {
48
    ios::sync_with_stdio(false);
49
    cin.tie(nullptr);
50
51
    long long a, m;
52
    if (!(cin >> a >> m)) return 0;
53
    long long inv = mod_inverse_totient(a, m);
54
    if (inv == -1) cout << "No inverse\n";
55
    else cout << inv << "\n";
56
    return 0;
57
}
58