首页 > 其他分享 >城中分支

城中分支

时间：2024-10-07 22:23:45浏览次数：7  
标签：城中 leq int ++ mp minp id 分支

城中分支

题目描述

“城市处于建设中......”

预言之子的你获得了一个拥有 $n$ 个元素的数组。 天神赋予你 $q$ 次操作：

  1. $Modify$，$l$，$r$，$x$------对于每个 $i$ $(l \leq i \leq r)$，将 $a_i$ 乘以 $x$ 。
  2. $Query$，$l$，$r$------你需要回答 $\varphi(\prod_{i=l}^{r}{a_i})$ 取模 $10^9+7$，其中 $\varphi$ 表示欧拉函数。

正整数 $n$（表示为 $\varphi(n)$）的欧拉函数是满足 $\gcd(n,x)=1$ 的整数 $x$ $(1 \leq x \leq n)$ 的数量。

$\prod_{i=l}^{r}{a_i}$ 表示 $a_l \times a_{l+1} \times \cdots \times a_r$。

输入描述:

第一行包含两个整数 $n$ 和 $q$ $(1 \leq n \leq 4 \cdot 10^5 ,1 \leq q \leq 2 \cdot 10^5)$ — 数组中的元素数和查询数。

第二行包含 $n$ 个整数 $a_1, a_2, \ldots ,a_n$ $(1 \leq a_i \leq 300)$ — 数组 $a$ 的元素。

接下来是 $q$ 行以语句中给出的格式描述查询。

$Modify$，$l$，$r$，$x$ $(1 \leq l \leq r \leq n, 1\leq x \leq 300)$ —表示修改操作。

$Query$，$l$，$r$ $(1 \leq l \leq r \leq n)$ ——表示对欧拉函数值的查询操作。

数据保证至少有一个 $Query$ 查询。

输出描述:

对于每个 $Query$ 查询，打印其答案对 $10^9+7$ 取模的结果。

示例1

输入

4 4
5 9 1 2
Query 3 3
Query 3 4
Modify 4 4 3
Query 4 4

输出

1
1
2

示例2

输入

1 1
4
Query 1 1

输出

2

 

解题思路

  代码巨长巨难写，卡了快 3 个小时，不是 TLE 就是 MLE。

  首先有欧拉函数公式 $\varphi(x) = x \left(1 - \frac{1}{P_0}\right)\left(1 - \frac{1}{P_1}\right) \cdots \left(1 - \frac{1}{P_k}\right)$，其中 $x = P_{0}^{\alpha_{0}}P_{1}^{\alpha_{1}} \cdots P_{k}^{\alpha_{k}}$。因此有 $\varphi(x) = P_0^{\alpha_0} \left(1 - \frac{1}{P_0}\right) \cdot P_1^{\alpha_1} \left(1 - \frac{1}{P_1}\right) \cdots \cdot P_k^{\alpha_k} \left(1 - \frac{1}{P_k}\right) = \varphi(P_{0}^{\alpha_0}) \varphi(P_{1}^{\alpha_1}) \cdots \varphi(P_{k}^{\alpha_k})$。

  显然需要用到线段树，但我们既不可以直接维护区间的乘积（显然爆 long long），又不可以对乘积取模（否则求不了欧拉函数）。注意到 $a_i$ 和 $x$ 都不超过 $300$，而 $300$ 内的质数只有 $62$ 个，意味着乘积的结果均可以表示成 $P_{0}^{\alpha_{0}}P_{1}^{\alpha_{1}} \cdots P_{61}^{\alpha_{61}}$，因此我们可以转向去维护乘积结果的各个质因子的数量即 $\alpha_{i}$。

  定义线段树节点信息：

struct Node {
    int l, r;
    array<LL, 62> s, sum;
};

  当需要给节点维护的整个区间乘上 $x = P_{0}^{\alpha_{0}}P_{1}^{\alpha_{1}} \cdots P_{61}^{\alpha_{61}}$ 时，只需更新 $s_i \gets s_i + \alpha_{i}(r-l+1)$，$\text{sum}_i \gets \text{sum}_i + \alpha_i$ $(0 \leq i < 62)$（$\text{sum}$ 是懒标记）。

  查询时，我们累加询问区间内每个质因子的次数，用大小为 $62$ 的数组 $s$ 表示。乘积的欧拉函数就是 $\prod\limits_{i=0}^{61} [s_i > 0] \, P_i^{s_i} \left(1 - \frac{1}{P_i} \right)$。

  上述做法的时间复杂度为 $O\left( n \log{A} + q\log{n}(\log{A} + \pi(A)\log{(q\log{A})}) \right)$，空间复杂度为 $O(n \pi(A))$。然而实际上线段树所需要的内存空间为 1k+ MB！上述做法肯定过不了。

  用不了线段树然后我就投机取巧用分块，结果空间是变小了但 TLE。做法和上面类似，每个块维护各个质因子的数量，具体做法就不详述了。分块的时间复杂度为 $O\left( n \log{A} + q\sqrt{n}(\log{A} + \pi(A)\log{(q\log{A})}) \right)$，空间复杂度为 $O(n \pi(A))$ 但常数比上面的小非常多。

  分块做法 TLE 代码如下：

查看代码 
#include <bits/stdc++.h>
using namespace std;

typedef long long LL;

const int N = 4e5 + 5, M = 305, B = 640, mod = 1e9 + 7;

int a[N][62];
int prime[M], mp[M], minp[M], cnt;
bool vis[M];
int id[N];
LL s[B][M], sum[B][M], c[M];

void get_prime(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[cnt] = i;
            mp[i] = cnt++;
            minp[i] = i;
        }
        for (int j = 0; prime[j] * i <= n; j++) {
            vis[prime[j] * i] = true;
            minp[prime[j] * i] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
}

int qmi(int a, LL k) {
    int ret = 1;
    while (k) {
        if (k & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
        k >>= 1;
    }
    return ret;
}

void modify(int l, int r, int x) {
    if (id[l] == id[r]) {
        for (int i = l; i <= r; i++) {
            int t = x;
            while (t > 1) {
                a[i][mp[minp[t]]]++;
                s[id[i]][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
        
    }
    else {
        for (int i = l; id[i] == id[l]; i++) {
            int t = x;
            while (t > 1) {
                a[i][mp[minp[t]]]++;
                s[id[i]][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
        for (int i = r; id[i] == id[r]; i--) {
            int t = x;
            while (t > 1) {
                a[i][mp[minp[t]]]++;
                s[id[i]][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
        for (int i = id[l] + 1; i < id[r]; i++) {
            int t = x;
            while (t > 1) {
                s[i][mp[minp[t]]] += B;
                sum[i][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
    }
}

int query(int l, int r) {
    memset(c, 0, sizeof(c));
    if (id[l] == id[r]) {
        for (int i = l; i <= r; i++) {
            for (int j = 0; j < cnt; j++) {
                c[j] += a[i][j] + sum[id[i]][j];
            }
        }
    }
    else {
        for (int i = l; id[i] == id[l]; i++) {
            for (int j = 0; j < cnt; j++) {
                c[j] += a[i][j] + sum[id[i]][j];
            }
        }
        for (int i = r; id[i] == id[r]; i--) {
            for (int j = 0; j < cnt; j++) {
                c[j] += a[i][j] + sum[id[i]][j];
            }
        }
        for (int i = id[l] + 1; i < id[r]; i++) {
            for (int j = 0; j < cnt; j++) {
                c[j] += s[i][j];
            }
        }
    }
    int ret = 1;
    for (int i = 0; i < cnt; i++) {
        if (c[i]) ret = ret * (prime[i] - 1ll) % mod * qmi(prime[i], c[i] - 1) % mod;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    get_prime(M - 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        id[i] = (i - 1) / B + 1;
        while (x > 1) {
            a[i][mp[minp[x]]]++;
            s[id[i]][mp[minp[x]]]++;
            x /= minp[x];
        }
    }
    while (m--) {
        string s;
        cin >> s;
        if (s[0] == 'M') {
            int l, r, x;
            cin >> l >> r >> x;
            modify(l, r, x);
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << '\n';
        }
    }
    
    return 0;
}

  下面给出正解了，还是用到线段树。细想一下，最开始的线段树做法会 MLE，正是因为我们给每个节点都开了大小为 $62$ 的数组去统计各个质因子的数量，而我们有必要去记录质因子的数量吗？回想欧拉函数 $\varphi(x) = x \left(1 - \frac{1}{P_0}\right)\left(1 - \frac{1}{P_1}\right) \cdots \left(1 - \frac{1}{P_k}\right)$，我们只要分别知道对应区间乘积的结果（可以取模），以及乘积结果（不取模）所含有的质因子，就可以计算欧拉函数。可以发现我们并不需要统计各个质因子的数量，只需统计出现了哪些质因子即可，这个可以用一个 long long 变量来状态压缩统计。

  为此重新定义线段树节点信息：

struct Node {
    int l, r;
    int p, prod;
    LL s, sum;
};

  其中 $p$ 是区间乘积取模后的结果，$\text{prod}$ 是对应的区间乘懒标记。$s$ 是状态压缩表示区间乘积（没取模）包含的质因子，$\text{sum}$ 是对应的区间加懒标记。节点更新以及懒标记下传请参考代码，这里就不过多赘述了。

  AC 代码如下，时间复杂度为 $O(n \log{A} + q (\log{n} + \pi(A)))$，空间复杂度为 $O(n)$：

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

typedef long long LL;

const int N = 4e5 + 5, M = 305, B = 640, mod = 1e9 + 7;

int a[N][62];
int prime[M], mp[M], minp[M], cnt;
bool vis[M];
int id[N];
LL s[B][M], sum[B][M], c[M];

void get_prime(int n) {
    for (int i = 2; i <= n; i++) {
        if (!vis[i]) {
            prime[cnt] = i;
            mp[i] = cnt++;
            minp[i] = i;
        }
        for (int j = 0; prime[j] * i <= n; j++) {
            vis[prime[j] * i] = true;
            minp[prime[j] * i] = prime[j];
            if (i % prime[j] == 0) break;
        }
    }
}

int qmi(int a, LL k) {
    int ret = 1;
    while (k) {
        if (k & 1) ret = 1ll * ret * a % mod;
        a = 1ll * a * a % mod;
        k >>= 1;
    }
    return ret;
}

void modify(int l, int r, int x) {
    if (id[l] == id[r]) {
        for (int i = l; i <= r; i++) {
            int t = x;
            while (t > 1) {
                a[i][mp[minp[t]]]++;
                s[id[i]][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
        
    }
    else {
        for (int i = l; id[i] == id[l]; i++) {
            int t = x;
            while (t > 1) {
                a[i][mp[minp[t]]]++;
                s[id[i]][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
        for (int i = r; id[i] == id[r]; i--) {
            int t = x;
            while (t > 1) {
                a[i][mp[minp[t]]]++;
                s[id[i]][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
        for (int i = id[l] + 1; i < id[r]; i++) {
            int t = x;
            while (t > 1) {
                s[i][mp[minp[t]]] += B;
                sum[i][mp[minp[t]]]++;
                t /= minp[t];
            }
        }
    }
}

int query(int l, int r) {
    memset(c, 0, sizeof(c));
    if (id[l] == id[r]) {
        for (int i = l; i <= r; i++) {
            for (int j = 0; j < cnt; j++) {
                c[j] += a[i][j] + sum[id[i]][j];
            }
        }
    }
    else {
        for (int i = l; id[i] == id[l]; i++) {
            for (int j = 0; j < cnt; j++) {
                c[j] += a[i][j] + sum[id[i]][j];
            }
        }
        for (int i = r; id[i] == id[r]; i--) {
            for (int j = 0; j < cnt; j++) {
                c[j] += a[i][j] + sum[id[i]][j];
            }
        }
        for (int i = id[l] + 1; i < id[r]; i++) {
            for (int j = 0; j < cnt; j++) {
                c[j] += s[i][j];
            }
        }
    }
    int ret = 1;
    for (int i = 0; i < cnt; i++) {
        if (c[i]) ret = ret * (prime[i] - 1ll) % mod * qmi(prime[i], c[i] - 1) % mod;
    }
    return ret;
}

int main() {
    ios::sync_with_stdio(false);
    cin.tie(nullptr);
    int n, m;
    cin >> n >> m;
    get_prime(M - 1);
    for (int i = 1; i <= n; i++) {
        int x;
        cin >> x;
        id[i] = (i - 1) / B + 1;
        while (x > 1) {
            a[i][mp[minp[x]]]++;
            s[id[i]][mp[minp[x]]]++;
            x /= minp[x];
        }
    }
    while (m--) {
        string s;
        cin >> s;
        if (s[0] == 'M') {
            int l, r, x;
            cin >> l >> r >> x;
            modify(l, r, x);
        }
        else {
            int l, r;
            cin >> l >> r;
            cout << query(l, r) << '\n';
        }
    }
    
    return 0;
}

 

参考资料

  沈阳化工大学第十一届程序设计沈阳区竞赛 thisislike_fan 提交的代码：https://ac.nowcoder.com/acm/contest/view-submission?submissionId=71790420

标签：城中,leq,int,++,mp,minp,id,分支
From： https://www.cnblogs.com/onlyblues/p/18450757

相关文章

  • Git分支-团队协作以及GitHub操作
    Git分支操作在版本控制过程中，同时推进多个任务==>程序员开发与开发主线并行，互不影响分支底层也是指针的引用hot-fix:相当于若在进行分支合并后程序出现了bug和卡顿等现象，通过热补丁来进行程序的更新，确保程序正常运行常用操作命令命令作用gitbranch分支名创建......
  • IDEA如何对比不同分支某个文件的差异
    前言我们在使用IDEA开发时，经常是和Git一起使用的，这样能方便的管理我们的代码。git的一个特点就是可以有很多分支，这些分支能让我们区分不同的功能等，非常方便。有时候，我们需要查看下某个文件中，当前分支与某个分支的差异，应该如何操作呢？如何查看不同分支的git差异首先，我们找到我......
  • 运算符、分支语句
    位操作符：可以直接操作二进制数位的内容；~是一个单目位操作符，它可以根据一个数字计算另外一个数字，这两个数字所有二进制数位的内容都不同（按位取反），使用的时候这个符号应该写在数字前面双目位操作符：包括按位与（&），按位或（|）以及按位异或（^）,他们都可以把两个数字对应二进制数位的内容做计算......
  • 【C语言】分支和循环
    个人主页：zxctscl如有转载请先通知文章目录前言1.if语句1.1if1.2else1.3分支中包含多条语句1.4嵌套if1.5悬空else问题2.关系操作符3.逻辑操作符：&&||！3.1逻辑取反运算符（！）3.2与运算符（&&）3.3或运算符（||）3.4举例3.5短路4.switch语句4.1if语句和switch语......
  • Gitlab分支管理规范和提交代码规范
    gitlab分支管理规范分支说明：测试代码库共有三个分支，main分支、dev分支、release分支--main分支：存放运行稳定的最新代码，一般不直接将未审核的代码合入到main分支--dev分支：存放个人开发的用例脚本，可用于用例故障修复，新的用例开发等--release分支：对应上线的产品版本，在发布......
  • Git 与远程分支
    90.远程仓库和分支我们经常需要对远程仓库里的分支进行更新。‍当从远程库clone时，默认情况下，只会拉取master​分支，并且会将本地的master分支和远程的master分支关联起来：$gitbranch*master‍‍推送本地分支推送分支，就是把该分支上的所有本地提交推送到远程库......
  • 掌握 Git：如何删除本地、合并和远程分支
    在软件开发领域，有效的版本控制对于确保顺利协作和项目管理至关重要。Git是使用最广泛的版本控制系统之一，了解如何有效地处理分支可以节省时间并防止错误。在本文中，我们将探讨如何管理本地、合并和远程Git分支，重点关注有助于简化工作流程的命令。删除本地Git分支在处理项目时......
  • 20240924_082514 c语言 switch分支结构
    语法演练体验switch的用法比较多路if一个个的比vs精准定位case穿透体验没有break的情况......
  • 20240924_072514 c语言 分支结构
    关于分支情况不同进行不同的事件生活中的分支判断天气判断生命值判断VIP判断病假用法二路分支多路分支......
  • Git 分支管理全攻略：一篇博客带你玩转代码分支！
    什么是分支？在Git里，分支其实就有点像一个树的枝杈，每个分支上可以有不同的文件的版本，并且不会互相干扰。​分支功能有什么用？在工作中，我们经常是需要和别人一起开发一个项目的，此时可能你开发A功能，别人开发B功能；如果只有一个分支的话，那么所有人都得在这个分支上干活；如果你开发......

赞助商

阅读排行

网站主页关于我们联系我们网站地图

本网站内容转载自其他媒体，侵权联系[admin##ips99.com]。

Copyright © 2020-2023 IPS99 版权所有 IPS99