H.Set

随机。

#include <bits/stdc++.h>
using namespace std;
int main(int argc, char *argv[]) {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    int k, r;
    cin >> k >> r;
    vector<int> T;
    int cnt1 = (512 - 1) / r + 1;
    for (int i = 1; i <= 256; ++i) {
        T.push_back(i <= cnt1 ? 1 : 0);
    }
    for (int i = 1; i <= k; ++i) {
        for (auto it: T) {
            cout << it;
        }
        cout << '\n';
        random_shuffle(T.begin(), T.end());
    }
    system("pause");
    return 0;
}

L.Euler Function

根据线性递推求欧拉函数我们可以得到以下结论：

对于要乘上的\(w\)我们对它分解质因数，先考虑单点\(x\)的情况，我们遍历\(w\)的所有质因子\((例如4的所有质因子包括[2,2])\)​，假如当前遍历到的为\(i\)：

\(\bullet\) \(x\%i=0\)：\(\phi(x \cdot i) = \phi(x) \cdot i\)

\(\bullet\) \(x\%i!=0\)：\(\phi(x \cdot i) = \phi(x) \cdot (i-1)\)

对于区间乘我们可以分两种情况考虑，假如当前遍历的因子是\(i\)：

\(\bullet\) 区间内每个数都有这个因子，那么我们只需要执行区间乘操作。

\(\bullet\) 否则我们直接单点暴力更新，单点乘上\(i-1\)，同时给这个点的标记数组加上\(i\)这个因子。

那么本题就可以用线段树解决了，对于标记数组，可以考虑用\(bitset\)实现，这样上推的时候只需要左右儿子的\(bitset\&\)一下就可以了。

#include <bits/stdc++.h>
using namespace std;

#define int long long
const int MAXN = 1e5 + 5;
const int MOD = 998244353;

bool isNotPrime[MAXN]; // 是否是质数
int phi[MAXN]; // 欧拉函数
int prime[MAXN], idx; // 质数
void seive(int _MAXN) {
    phi[1] = 1;
    for (int i = 2; i < _MAXN; ++i) {
        if (!isNotPrime[i]) {
            phi[i] = i - 1;
            prime[++idx] = i;
        }
        for (int j = 1; j <= idx && i * prime[j] < _MAXN; ++j) {
            isNotPrime[i * prime[j]] = true;
            // 情况一
            if (i % prime[j] == 0) {
                phi[i * prime[j]] = phi[i] * prime[j];
                break;
            }
            // 情况二
            else {
                phi[i * prime[j]] = phi[i] * (prime[j] - 1);
            }
        }
    }
}
void divide(bitset<100>&bit, int x) {
    for (int i = 2; i * i <= x; ++i) {
        if (x % i == 0) {
            bit[i] = 1;
            while (x % i == 0) {
                x /= i;
            }
        }
    }
    if (x > 1) {
        bit[x] = 1;
    }
}

int a[MAXN];

#define ls(x) (x) << 1
#define rs(x) (x) << 1 | 1
struct Node {
    int l, r, val, mul;
    bitset<100> bit;
    int mid() {
        return (l + r) >> 1;
    }
    int len() {
        return r - l + 1;
    }
    void update(int x) {
        if (x) {
            val = (val * x) % MOD;
            mul = (mul * x) % MOD;
        }
    }
} tree[MAXN << 2];
void pushup(int p) {
    tree[p].bit = tree[ls(p)].bit & tree[rs(p)].bit;
    tree[p].val = (tree[ls(p)].val + tree[rs(p)].val) % MOD;
}
void pushdown(int p) {
    tree[ls(p)].update(tree[p].mul);
    tree[rs(p)].update(tree[p].mul);
    tree[p].mul = 1;
}
void build(int l, int r, int p) {
    tree[p].l = l, tree[p].r = r, tree[p].mul = 1;
    if (l == r) {
        tree[p].val = phi[a[l]];
        // 先将当前给定数组的因子全部保存下来
        divide(tree[p].bit, a[l]);
        return ;
    }
    int mid = (l + r) >> 1;
    build(l, mid, ls(p));
    build(mid + 1, r, rs(p));
    pushup(p);
}
void modify(int l, int r, int k, int p) {
    if (l <= tree[p].l && tree[p].r <= r) {
        if (tree[p].bit[k]) {
            tree[p].update(k);
            return ;
        }
        if (tree[p].l == tree[p].r) {
            tree[p].bit[k] = 1;
            tree[p].update(k - 1);
            return ;
        }
    }
    pushdown(p);
    int mid = tree[p].mid();
    if (l <= mid) modify(l, r, k, ls(p));
    if (r > mid) modify(l, r, k, rs(p));
    pushup(p);
}
int query(int l, int r, int p) {
    if (l <= tree[p].l && tree[p].r <= r) {
        return tree[p].val;
    }
    pushdown(p);
    int mid = tree[p].mid(), res = 0;
    if (l <= mid) res = (res + query(l, r, ls(p))) % MOD;
    if (r > mid) res = (res + query(l, r, rs(p))) % MOD;
    return res;
}
signed main(int argc, char *argv[]) {
    ios::sync_with_stdio(false), cin.tie(0), cout.tie(0);
    seive(105);
    int n, m;
    cin >> n >> m;
    for (int i = 1; i <= n; ++i) {
        cin >> a[i];
    }
    build(1, n, 1);
    while (m--) {
        int opt, l, r, w;
        cin >> opt >> l >> r;
        if (opt == 1) {
            cout << query(l, r, 1) << '\n';
        }
        else {
            cin >> w;
            for (int i = 2; i * i <= w; ++i) {
                int cnt = 0;
                while (w % i == 0) {
                    ++cnt;
                    w /= i;
                }
                while (cnt--) {
                    modify(l, r, i, 1);
                }
            }
            if (w > 1) {
                modify(l, r, w, 1);
            }
        }
    }
    system("pause");
    return 0;
}