pintia The 2021 ICPC Asia Regionals Online Contest (II) L Euler Function

Posted on Edited on In

ProblemSet Problem - L Euler Function

Given as a prime,

  1. we have when is a fator of ;
  2. otherwise, we have .
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
#include <cstdio>
#include <bitset>
using namespace std;
using LL = long long;
const int N = 100001, MOD = 998244353;
int tot, n, m, t, l, r, w, a[N], primes[26], // primes within 100.
cnt[101][26], // cnt[i][j], how many jth prime does number i contain.
phi[101]; // value of Eular Function.
bitset<26> st[101]; // st[i][j], if number i is divisible to the jth prime.
bool isComposite[101];
struct Node {
    int l, r;
    LL mul, sum;
    bitset<26> mark; // cnt[i], if the ith prime is the common prime factor to a[l]~a[r].
} tr[N << 2];
int cal_phi(int n) {
    int ans = n;
    for (int i = 2; i <= n / i; ++i) {
        if (n % i == 0) {
            ans = ans / i * (i - 1);
            while (n % i == 0) n /= i;
        }
    }
    if (n > 1) ans = ans / n * (n - 1);
    return ans;
}
LL qmi(LL a, LL b, LL mod) {
    LL ans = 1ll;
    while (b) {
        if (b & 1) ans = ans * a % MOD;
        b >>= 1;
        a = a * a % MOD;
    }
    return ans % MOD;
}
void init() { // init primes[], cnt[][], st[].
    int n = 100;
    for (int i = 2; i <= n; ++i) {
        if (!isComposite[i]) primes[++tot] = i;
        for (int j = 1; primes[j] <= n / i; ++j) {
            isComposite[primes[j] * i] = true;
            if (i % primes[j] == 0) break;
        }
    }
    for (int i = 1; i <= 100; ++i) {
        for (int j = 1; j <= tot; ++j) {
            int tmp = i;
            while (tmp % primes[j] == 0) {
                ++cnt[i][j];
                tmp /= primes[j];
            }
            st[i][j] = cnt[i][j];
        }
    }
    for (int i = 1; i <= 100; ++i) phi[i] = cal_phi(i);
}
void pushup(int u) {
    tr[u].sum = (tr[u << 1].sum + tr[u << 1 | 1].sum) % MOD;
    tr[u].mark = tr[u << 1].mark & tr[u << 1 | 1].mark;
}
void pushdown(int u) {
    if (tr[u].mul != 1) {
        tr[u << 1].mul = (tr[u << 1].mul * tr[u].mul) % MOD;
        tr[u << 1].sum = (tr[u << 1].sum * tr[u].mul) % MOD;
        tr[u << 1 | 1].mul = (tr[u << 1 | 1].mul * tr[u].mul) % MOD;
        tr[u << 1 | 1].sum = (tr[u << 1 | 1].sum * tr[u].mul) % MOD;
        tr[u].mul = 1;
    }
}
void build(int u, int l, int r) {
    tr[u] = {l, r, 1, 0};
    if (l == r) {
        tr[u].sum = phi[a[l]], tr[u].mark = st[a[l]];
        return;
    }
    int mid = l + r >> 1;
    build(u << 1, l, mid), build(u << 1 | 1, mid + 1, r);
    pushup(u);
}
LL query(int u, int l, int r) {
    if (l <= tr[u].l && tr[u].r <= r) return tr[u].sum;
    pushdown(u);
    int ans = 0, mid = tr[u].l + tr[u].r >> 1;
    if (l <= mid) ans = query(u << 1, l, r) % MOD;
    if (r > mid) ans = (ans + query(u << 1 | 1, l, r)) % MOD;
    return ans;
}
// [l, r] * primes[pos] % MOD for k times.
void modify(int u, int l, int r, int pos, int k) {
    int p = primes[pos];
    if (l <= tr[u].l && tr[u].r <= r && tr[u].mark[pos]) {
            tr[u].sum = (tr[u].sum * qmi(p, k, MOD)) % MOD;
            tr[u].mul = (tr[u].mul * qmi(p, k, MOD)) % MOD;
    } else if (tr[u].l == tr[u].r) {
        tr[u].sum = (tr[u].sum * (p - 1)) % MOD;
        tr[u].mark[pos] = 1;
        tr[u].sum = (tr[u].sum * qmi(p, k - 1, MOD)) % MOD;
    } else {
        pushdown(u);
        int mid = tr[u].l + tr[u].r >> 1;
        if (l <= mid) modify(u << 1, l, r, pos, k);
        if (r > mid) modify(u << 1 | 1, l, r, pos, k);
        pushup(u);
    }
}
int main() {
    init();
    scanf("%d%d", &n, &m);
    for (int i = 1; i <= n; ++i) scanf("%d", &a[i]);
    build(1, 1, n);
    while (m--) {
        scanf("%d%d%d", &t, &l, &r);
        if (t == 1) {
            printf("%lld\n", query(1, l, r));
        } else {
            scanf("%d", &w);
            for (int i = 1; i <= tot; ++i)
                if (cnt[w][i]) modify(1, l, r, i, cnt[w][i]);
        }
    }
    return 0;
}