UOJ#38 奇数国题解

简要题意

有$100000$个数，每个数的质因子只会是前$60$个素数（$2 \sim 281$）。一开始每个数都是$3$，有$x$个操作，每次要么修改一个数，要么询问一段区间内的数的乘积的欧拉函数模$19961993$的值。$x \leqslant 100000$，过程中每个数不会超过$1000000$，每次询问的乘积不会超过$10^{18}$。

题♂解♂

虽然这个题目非常地神，鉴于网上的题解都很神，我这个退役选手只能自己写一份题♂解♂造福大众辣。

根据欧拉函数的性质，设$\displaystyle a=\prod_{i=1}^{60}p_i^{k_i}$，那么$\displaystyle \varphi(a)=\prod_{i=1}^{60}\left(p_i^{k_i-1}(p_i-1)\quad | k_i>0\right)=\left[\prod_{i=1}^{60}\left(p_i^{k_i-1}\quad |k_i>0 \right)\right]\cdot \left[\prod_{i=1}^{60}\left(p_i-1\quad |k_i>0\right)\right]$。

这个东西用线段树直接维护非常烦，我们把相同格式的分开来维护。

设$\displaystyle \alpha(a)=\prod_{i=1}^{60}\left(p_i^{k_i-1}\quad |k_i>0 \right)$，那么：

$\displaystyle \varphi(a)=\alpha(a)\prod_{i=1}^{60}\left(p_i-1 \quad | \quad p_i | a\right)$

$\displaystyle \alpha(ab)=\alpha(a)\alpha(b)\prod_{i=1}^{60}\left(p_i \quad | \quad p_i|a 且 p_i|b\right)$

$\displaystyle \varphi(ab)=\alpha(ab)\prod_{i=1}^{60}\left(p_i-1 \quad | \quad p_i|a 或 p_i|b\right)$

于是线段树上只要维护$\alpha(当前域的乘积)$和当前域的乘积是否含每个质因子。为了快速求后面的那两个乘积，我们还可以每$20$个质因子状态压一个位，预处理$p_i$和$p_i-1$的乘积，线段树上用$\mathrm{and}$和$\mathrm{or}$合并状态即可。

时间复杂度$\mathcal{O}(x \log_2100000)$。

代码（C++）

#include <bits/stdc++.h>
using namespace std;
const int N = 100005, M = 282, pm = 19961993, L = 2000005, TM1 = (1 << 19) + 1, TM2 = (1 << 20) + 1;
char buf[L], *p = buf;
void rd(int &t) {
    t = 0;
    while (*p < 48 || *p > 57) ++p;
    do {(t *= 10) += *p - 48; ++p;} while (*p > 47 && *p < 58);
}
bool vis[M];
int cnt[60], q[M], fun[TM1], pro1[TM2], pro2[TM2], pro3[TM2], alp1[TM2], alp2[TM2], alp3[TM2];
struct ans {
    int alpha, s1, s2, s3;
} tmp;
ans mge(ans a, ans b) {
    return (ans){1LL * a.alpha * b.alpha % pm * pro1[a.s1 & b.s1] % pm * pro2[a.s2 & b.s2] % pm * pro3[a.s3 & b.s3] % pm,
        a.s1 | b.s1, a.s2 | b.s2, a.s3 | b.s3};
}
struct seg {
    int alpha, s1, s2, s3;
    seg *lc, *rc;
    void init() {s1 = 2; s2 = s3 = 0; alpha = 1;}
    void upd() {
        s1 = lc -> s1 | rc -> s1; s2 = lc -> s2 | rc -> s2; s3 = lc -> s3 | rc -> s3;
        int t1 = lc -> s1 & rc -> s1, t2 = lc -> s2 & rc -> s2, t3 = lc -> s3 & rc -> s3;
        alpha = 1LL * lc -> alpha * rc -> alpha % pm * pro1[t1] % pm * pro2[t2] % pm * pro3[t3] % pm;
    }
    void mdf(int l, int r, int x, int y, int ts1, int ts2, int ts3) {
        if (l == r) {alpha = y; s1 = ts1; s2 = ts2; s3 = ts3; return;}
        int mid = l + r >> 1;
        if (x <= mid) lc -> mdf(l, mid, x, y, ts1, ts2, ts3); else rc -> mdf(mid + 1, r, x, y, ts1, ts2, ts3);
        upd();
    }
    ans qry(int l, int r, int ll, int rr) {
        if (ll <= l && r <= rr) return (ans){alpha, s1, s2, s3};
        int mid = l + r >> 1;
        if (rr <= mid) return lc -> qry(l, mid, ll, rr);
        if (ll > mid) return rc -> qry(mid + 1, r, ll, rr);
        return mge(lc -> qry(l, mid, ll, rr), rc -> qry(mid + 1, r, ll, rr));
    }
} *rt, pool[N * 2], *tail = pool;
void build(seg *&rt, int l, int r) {
    rt = tail++;
    if (l == r) {rt -> init(); return;}
    int mid = l + r >> 1;
    build(rt -> lc, l, mid); build(rt -> rc, mid + 1, r);
    rt -> upd();
}
int main() {
    int r = 0, i, j, S, t, op, x, y, tq, s1, s2, s3;
    for (i = 2; i < M; ++i) {
        if (!vis[i]) q[r++] = i;
        for (j = 0; j < r && i * q[j] < M; ++j) {
            vis[i * q[j]] = true;
            if (!(i % q[j])) break;
        }
    }
    for (i = 0; i < 20; ++i) fun[1 << i] = i;
    pro1[0] = pro2[0] = pro3[0] = alp1[0] = alp2[0] = alp3[0] = 1;
    for (S = 1; S < (1 << 20); ++S) {
        t = S & -S; i = fun[t];
        pro1[S] = 1LL * pro1[S - t] * q[i] % pm;
        pro2[S] = 1LL * pro2[S - t] * q[20 + i] % pm;
        pro3[S] = 1LL * pro3[S - t] * q[40 + i] % pm;
        alp1[S] = 1LL * alp1[S - t] * (q[i] - 1) % pm;
        alp2[S] = 1LL * alp2[S - t] * (q[20 + i] - 1) % pm;
        alp3[S] = 1LL * alp3[S - t] * (q[40 + i] - 1) % pm;
    }
    fread(buf, 1, L, stdin);
    build(rt, 1, N - 5);
    rd(tq);
    while (tq--) {
        rd(op); rd(x); rd(y);
        if (op) {
            memset(cnt, 0, sizeof(cnt));
            s1 = s2 = s3 = 0;
            for (i = 0; i < r; ++i)
                if (!(y % q[i])) {
                    if (i < 20) s1 |= 1 << i; else if (i < 40) s2 |= 1 << (i - 20); else s3 |= 1 << (i - 40);
                    while (!(y % q[i])) {y /= q[i]; ++cnt[i];}
                }
            for (i = 0; i < r; ++i)
                for (j = 1; j < cnt[i]; ++j) y *= q[i];
            rt -> mdf(1, N - 5, x, y, s1, s2, s3);
        } else {
            tmp = rt -> qry(1, N - 5, x, y); s1 = tmp.s1; s2 = tmp.s2; s3 = tmp.s3;
            printf("%d\n", 1LL * tmp.alpha * alp1[s1] % pm * alp2[s2] % pm * alp3[s3] % pm);
        }
    }
    return 0;
}

完结撒花！

zhourunlong的博客

博客