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], cnt[101][26], phi[101]; bitset<26> st[101]; bool isComposite[101]; struct Node { int l, r; LL mul, sum; bitset<26> mark; } 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() { 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; }
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; }
|