【Codeforces 1114F】Please, another Queries on Array?

题目链接:Codeforces Round #538 (Div. 2) - Problem F

描述

You are given an array $a_1, a_2, \ldots, a_n$.

You need to perform $q$ queries of the following two types:

  1. "MULTIPLY l r x" — for every $i$ ($l \le i \le r$) multiply $a_i$ by $x$.
  2. "TOTIENT l r" — print$\varphi(\prod \limits_{i=l}^{r} a_i)$ taken modulo $10^9+7$, where $\varphi$ denotes Euler’s totient function. The Euler’s totient function of a positive integer $n$ (denoted as $\varphi(n)$) is the number of integers $x$ ($1 \le x \le n$) such that $\gcd(n,x) = 1$

Input

The first line contains two integers $n$ and $q$ ($1 \le n \le 4 \cdot 10^5$, $1 \le q \le 2 \cdot 10^5$) — the number of elements in array $a$ and the number of queries.

The second line contains $n$ integers $a_1, a_2, \ldots, a_n$ ($1 \le a_i \le 300$) — the elements of array $a$.

Then $q$ lines follow, describing queries in the format given in the statement.

"MULTIPLY l r x" ($1 \le l \le r \le n$, $1 \le x \le 300$) — denotes a multiplication query. "TOTIENT l r" ($1 \le l \le r \le n$) — denotes a query on the value of Euler’s totient function. It is guaranteed that there is at least one "TOTIENT" query.

Output

For each "TOTIENT" query, print the answer to it.

Example

Input

4 4
5 9 1 2
TOTIENT 3 3
TOTIENT 3 4
MULTIPLY 4 4 3
TOTIENT 4 4

Output

1
1
2

Note

In the first example, $\varphi(1) = 1$ for the first query, $\varphi(2) = 1$ for the second query and $\varphi(6) = 2$ for the third one.

思路

  • 首先我们知道:若 $n = \prod\limits_{i = 1} ^ r p_i^{k_i}$,则 $\varphi(n) = \prod\limits_{i = 1} ^ r p_i ^ {k_i - 1} (p_i - 1) = n \prod\limits_{p | n}(1 - \frac{1}{p})$。其中 $p$ 是质数。

  • 方法一:根据最后的式子,我们只需要维护两个量:区间的乘积、区间的质因子。这可以分别使用两个线段树来维护和合并信息。由于 $300$ 内一共有 $62$ 个质数(打表可知),所以可以使用 long long 来压状态。然后就是正常的线段树打标记没什么好说的了。

  • 方法二:根据前面一个式子,我们可以分别维护每个质因子的个数来计算其对答案的贡献。这样需要开 $62$ 个线段树,妥妥MLE。 由于每个质因子是独立的,所以我们可以考虑将所有操作离线,分别处理每个质因子,这样就只需要开一个了。但是由于种种原因(似乎是线段树的常数太大),我是用两个树状数组完成区间加和查询区间和的。

代码

方法一

cpp
  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
#include <bits/stdc++.h>
using namespace std;
typedef long long ll;
const static int N = 1 << 19;
const static int mod = 1e9 + 7;
vector<int> p, invp;
ll Pow(ll a, ll n)
{
    ll t = 1;
    for (; n; n >>= 1, (a *= a) %= mod)
        if (n & 1) (t *= a) %= mod;
    return t;
}
inline bool isprime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return n != 1;
}
void init(int n)
{
    for (int i = 2; i <= n; i++)
        if (isprime(i)) p.push_back(i);
    for (auto t : p)
        invp.push_back(Pow(t, mod - 2));
}
ll gao(int x)
{
    ll ret = 0;
    for (int i = 0; i < p.size(); i++)
        if (x % p[i] == 0) ret |= (1LL << i);
    return ret;
}
namespace Segment_Tree
{
typedef long long type_t;
type_t pro[N << 2], bit[N << 2];
type_t mul[N << 2], tag[N << 2];
#define lson o << 1
#define rson o << 1 | 1
#define Lson l, m, lson
#define Rson m + 1, r, rson
inline void pushup(int o)
{
    pro[o] = (pro[lson] * pro[rson]) % mod;
    bit[o] = (bit[lson] | bit[rson]);
}
inline void pushdown(int o, int m)
{
    if (mul[o] != 1)
    {
        (mul[lson] *= mul[o]) %= mod;
        (mul[rson] *= mul[o]) %= mod;
        (pro[lson] *= Pow(mul[o], m - (m >> 1))) %= mod;
        (pro[rson] *= Pow(mul[o], m >> 1)) %= mod;
        mul[o] = 1;
    }
    if (tag[o] != 0)
    {
        tag[lson] |= tag[o];
        tag[rson] |= tag[o];
        bit[lson] |= tag[o];
        bit[rson] |= tag[o];
        tag[o] = 0;
    }
}
void build(int l = 1, int r = N, int o = 1)
{
    mul[o] = 1, tag[o] = 0;
    if (l == r)
    {
        scanf("%lld", &pro[o]);
        bit[o] = gao(pro[o]);
        return;
    }
    const int m = l + r >> 1;
    build(Lson);
    build(Rson);
    pushup(o);
}
void update(int L, int R, pair<type_t, type_t> v, int l = 1, int r = N, int o = 1)
{
    if (L <= l && r <= R)
    {
        (mul[o] *= v.first) %= mod;
        (pro[o] *= Pow(v.first, r - l + 1)) %= mod;
        tag[o] |= v.second;
        bit[o] |= v.second;
        return;
    }
    pushdown(o, r - l + 1);
    const int m = l + r >> 1;
    if (L <= m) update(L, R, v, Lson);
    if (m < R) update(L, R, v, Rson);
    pushup(o);
}
pair<type_t, type_t>& operator|=(pair<type_t, type_t>& a, const pair<type_t, type_t>& b)
{
    (a.first *= b.first) %= mod;
    a.second |= b.second;
}
pair<type_t, type_t> query(int L, int R, int l = 1, int r = N, int o = 1)
{
    if (L <= l && r <= R) return make_pair(pro[o], bit[o]);
    pushdown(o, r - l + 1);
    const int m = l + r >> 1;
    pair<type_t, type_t> ret = make_pair(1, 0);
    if (L <= m) ret |= query(L, R, Lson);
    if (m < R) ret |= query(L, R, Rson);
    return ret;
}
#undef lson
#undef rson
#undef Lson
#undef Rson
}; // namespace Segment_Tree
int main()
{
    init(300);
    int n, q;
    scanf("%d%d", &n, &q);
    Segment_Tree::build(1, n, 1);
    for (int i = 0, l, r, x; i < q; i++)
    {
        static char op[10];
        scanf("%s%d%d", op, &l, &r);
        long long prod, bit;
        if (op[0] == 'T')
        {
            tie(prod, bit) = Segment_Tree::query(l, r, 1, n, 1);
            for (int i = 0; i < p.size(); i++)
                if (bit >> i & 1) prod = prod * (p[i] - 1) % mod * invp[i] % mod;
            printf("%lld\n", prod);
        }
        else
        {
            scanf("%d", &x);
            prod = x, bit = 0;
            for (int i = 0; i < p.size(); i++)
                if (x % p[i] == 0) bit |= 1LL << i;
            Segment_Tree::update(l, r, make_pair(prod, bit), 1, n, 1);
        }
    }
}

方法二

cpp
  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
#include <bits/stdc++.h>
using namespace std;

const int N = 4e5 + 5;
typedef long long ll;
ll num[N], sum[N];
const int mod = 1e9 + 7;
inline void update(int x, ll v, ll* bit)
{
    for (; x < N; x += x & -x) bit[x] += v;
}
inline ll query(int x, ll* bit)
{
    ll t = 0;
    for (; x; x -= x & -x) t += bit[x];
    return t;
}
vector<int> prime;
bool isprime(int n)
{
    for (int i = 2; i * i <= n; i++)
        if (n % i == 0) return false;
    return n != 1;
}
void init(int n)
{
    int tot = 0;
    for (int i = 2; i <= n; i++)
        if (isprime(i)) prime.push_back(i);
}
ll Pow(ll a, ll n)
{
    ll t = 1;
    for (; n; n >>= 1, (a *= a) %= mod)
        if (n & 1) (t *= a) %= mod;
    return t;
}
void update(int l, int r, ll x)
{
    update(l, x, num);
    update(r + 1, -x, num);
    update(l, 1LL * (l - 1) * x, sum);
    update(r + 1, 1LL * (-r) * x, sum);
}
ll query(int l, int r)
{
    return (1LL * r * query(r, num) - query(r, sum))
           - (1LL * (l - 1) * query(l - 1, num) - query(l - 1, sum));
}

int a[N];
int l[N], r[N], x[N];
ll ans[N];
int main()
{
    init(300);
    int n, q;
    scanf("%d%d", &n, &q);
    int M = prime.size();
    for (int i = 1; i <= n; i++) scanf("%d", &a[i]);
    for (int i = 0; i < q; i++)
    {
        static char op[10];
        scanf("%s%d%d", op, &l[i], &r[i]);
        if (op[0] == 'T')
            x[i] = -1;
        else
            scanf("%d", &x[i]);
        ans[i] = 1;
    }
    for (int t = 0; t < M; t++)
    {
        memset(num, 0, sizeof(num));
        memset(sum, 0, sizeof(sum));
        for (int i = 1; i <= n; i++)
        {
            int cnt = 0;
            while (a[i] % prime[t] == 0)
            {
                cnt++;
                a[i] /= prime[t];
            }
            if (cnt) update(i, i, cnt);
        }
        for (int i = 0; i < q; i++)
        {
            if (~x[i])
            {
                int cnt = 0;
                while (x[i] % prime[t] == 0)
                {
                    cnt++;
                    x[i] /= prime[t];
                }
                if (cnt) update(l[i], r[i], cnt);
            }
            else
            {
                ll cnt = query(l[i], r[i]);
                if (cnt)
                {
                    ans[i] = ans[i] * Pow(prime[t], cnt - 1) % mod;
                    ans[i] = ans[i] * (prime[t] - 1) % mod;
                }
            }
        }
    }
    for (int i = 0; i < q; i++)
        if (!~x[i]) printf("%lld\n", ans[i]);
}
Licensed under CC BY-NC-SA 4.0
最后更新于 2022 年 11 月 2 日 12:36 CST