2021ICPC网络赛第二场【L Euler Function】

发表于 更新于 分类于

2021ICPC网络赛第二场【L Euler Function】

势能线段树

img

img

分析：
根据欧拉函数的那个性质

1
2
3
4
5
if(p是质数)
{
	if(i % p == 0) f[i * p] = f[i] * p;
	else f[i * p] = f[i] * (p - 1);
}

  每次区间乘的那个数小于等于100，所以我们可以考虑把100以内的数质因数分解，区间乘100相当于区间乘两个2和两个5，但是根据那个性质，又分为了两种情况，到底需要乘p还是p - 1？对于每个区间我们可以维护一个bitset<30> tg，表示这个区间的数是否所有的都是第i个素数的倍数，显然，经过几次操作之后，大部分的区间的每个tg值都会变为1，此时都是乘p，比较像区间加/减lowbit的那个题(传送门)。这两道题用的这种线段树，据说是叫势能线段树来着好像。

  另外，用这个bitset，实际可以用bool数组的，但实测用bitset约250ms，bool数组490ms，另外bitset可以一下子赋值，不需要跑for循环一个一个的赋值

AC代码：

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
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
#include <bits/stdc++.h>

using namespace std;
typedef long long ll;

const ll mod = 998244353;
bitset<30> st[105];//st[i][j]表示数字i能否被第j个质数整除
struct node
{
    bitset<30> tg;
    ll x, lazy;
    int l, r;
} tree[400050];
int n, m;
int ar[100050];
int pri[30];//100以内的质数，一共25个
int cnt[105][30];//cnt[i][j]表示数字i质因数分解后需要cnt[i][j]个第j个质数
int f[105];//欧拉函数

void dio()//预处理数组pri和cnt
{
    int tot = 0;
    for(int i = 2; i <= 100; ++i)
    {
        bool flag = 0;
        for(int j = 2; j <= sqrt(i); ++j)
        {
            if(i % j == 0)
            {
                flag = 1;
                break;
            }
        }
        if(!flag) pri[++tot] = i;
    }
    for(int i = 1; i <= 100; ++i)
    {
        for(int j = 1; j <= 25; ++j)
        {
            int tmp = i;
            while(tmp % pri[j] == 0)
            {
                ++cnt[i][j];
                tmp /= pri[j];
            }
            st[i][j] = cnt[i][j];
        }
    }
}

int phi(int n)//计算欧拉函数
{
    int ans = n;
    for(int i = 2; i * i <= n; ++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;
}

void pushup(int p)
{
    tree[p].x = (tree[p<<1].x + tree[p<<1|1].x) % mod;
    tree[p].tg = (tree[p<<1].tg & tree[p<<1|1].tg);
}

void pushdown(int p)
{
    tree[p<<1].lazy = (tree[p<<1].lazy * tree[p].lazy) % mod;
    tree[p<<1|1].lazy = (tree[p<<1|1].lazy * tree[p].lazy) % mod;
    tree[p<<1].x = (tree[p<<1].x * tree[p].lazy) % mod;
    tree[p<<1|1].x = (tree[p<<1|1].x * tree[p].lazy) % mod;
    tree[p].lazy = 1;
}

void build(int p, int l, int r)
{
    tree[p].l = l;
    tree[p].r = r;
    tree[p].lazy = 1;
    if(tree[p].l == tree[p].r)
    {
        tree[p].x = 1ll * f[ar[l]];
        tree[p].lazy = 1;
        tree[p].tg = st[ar[l]];
        return ;
    }

    int mid = (l + r) >> 1;
    build(p<<1, l, mid);
    build(p<<1|1, mid + 1, r);
    pushup(p);
}

ll query(int p, int a, int b)
{
    if(a <= tree[p].l && tree[p].r <= b) return tree[p].x;

    if(tree[p].lazy != 1) pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(mid >= b) return query(p<<1, a, b);
    else if(mid < a) return query(p<<1|1, a, b);
    else return (query(p<<1, a, b) + query(p<<1|1, a, b)) % mod;
}

void updata(int p, int a, int b, int x, int y)
{
    if(a <= tree[p].l && tree[p].r <= b && tree[p].tg[x])
    {
        for(int i = 1; i <= y; ++i)
        {
            tree[p].x = (tree[p].x * pri[x]) % mod;
            tree[p].lazy = (tree[p].lazy * pri[x]) % mod;
        }
        return ;
    }

    if(tree[p].l == tree[p].r)
    {
        tree[p].x = (tree[p].x * (pri[x] - 1)) % mod;
        tree[p].tg[x] = 1;
        for(int i = 1; i <= y - 1; ++i) tree[p].x = (tree[p].x * pri[x]) % mod;
        return ;
    }

    if(tree[p].lazy != 1) pushdown(p);
    int mid = (tree[p].l + tree[p].r) >> 1;
    if(a <= mid) updata(p<<1, a, b, x, y);
    if(mid < b) updata(p<<1|1, a, b, x, y);
    pushup(p);
}

int main()
{
    dio();
    f[1] = 1;
    for(int i = 2; i <= 100; ++i) f[i] = phi(i);

    scanf("%d%d", &n, &m);
    for(int i = 1; i <= n; ++i) scanf("%d", &ar[i]);
    build(1, 1, n);
    int y, a, b, c;
    while(m--)
    {
        scanf("%d", &y);
        if(y == 1)
        {
            scanf("%d%d", &a, &b);
            printf("%lld\n", query(1, a, b) % mod);
        }
        else
        {
            scanf("%d%d%d", &a, &b, &c);
            for(int i = 1; i <= 25; ++i)
            {
                if(cnt[c][i]) updata(1, a, b, i, cnt[c][i]);
            }
        }
    }
    return 0;
}