2021ICPC網路賽第二場The 2021 ICPC Asia Regionals Online Contest (II) 【L Euler Function】

分析：
根據歐拉函式的那個性質

	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代碼：

#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;
}