当前位置: 首页 > news >正文

题解:P12128 [蓝桥杯 2024 省 B 第二场] 质数变革

link

很显然,这道题根本不需要根号分治,直接离线存下来一起修改就行。

我就来讲一下这道题为什么不用根号分治复杂度是对的吧。

如何暴力

显然可以把每次修改看做排名 \(+x\)\(-x\) 的操作,又因为这些修改的方式只有 \(n\) 种可能,我们可以用一个数组 \(c\) 存下所有 \(k\) 的修改,最后再一次性统计答案。

写成代码是这样的:

记录修改:

for(int i = 1, x, k, op; i <= q; i ++) {in(op, k, x);x = (op == 1 ? -x : x);c[k] += x;
}

最后统计:

for(int i = 1; i <= n; i ++) if(c[i]) for(int j = i; j <= n; j += i) sm[j] += c[i];

这样写复杂度是对的,而且是很好的复杂度,大概是 \(O(n\ln n)\)

为什么?

考虑对于一个数字 \(i\),它导致第二层循环跑几次?显然是 \(\frac ni\) 次,列成算式,总次数就是 \(\sum _{i = 1} ^{n} \lfloor \frac ni \rfloor\) 次,感性证明一下,原式(往坏里想,也就是去掉向下取整)可以变成 \(n\sum _{i = 1} ^{n} \frac 1i\),后面的东西是调和级数,是 \(\ln n\) 级别的,所以复杂度是上面的东西。

然后我们还可以发现对于一个质数,它的排名变化了就是变化了,而如果是一个合数,如果变化它的排名就只是把它变成相邻的质数,大概可以理解成如果第一次修改一个合数是让它的排名加一,就相当于是浪费了一次排名加一的机会让这个数变成了加一的那个质数,所以我们还要记录每个数第一次修改的方向。在记录修改的部分改改就行。

写成代码是这样的:

for(int i = 1, x, k, op; i <= q; i ++) {in(op, k, x);x = (op == 1 ? -x : x);c[k] += x;if(!vis[k]) for(int i = k; i <= n; i += k) !fis[i] ? fis[i] = op : 0; vis[k] = 1;
}

发现每一个 \(k\) 都只对它出现的第一次记录,复杂度仍如上所言,是 \(O(n\ln n)\)

再然后我们有了如上的东西,就可以快速的再写一个线性筛筛素数,在里面记录每一个数离它最近的两个质数。

再然后分讨一下,就可以输出答案了。

总复杂度 \(O(V + n\ln n)\)

// code by 樓影沫瞬_Hz17
#include <bits/stdc++.h>
using namespace std;#define getc() getchar_unlocked()
#define putc(a) putchar_unlocked(a)
#define en_ putc('\n')
#define e_ putc(' ')using pii = pair<int, int>;template<class T> inline T in() { T n = 0; char p = getc();while(p < '-') p = getc();bool f = p == '-' ? p = getc() : 0;do n = n * 10 + (p ^ 48), p = getc();while(isdigit(p));return f ? -n : n;
}
template<class T> inline T in(T &a) { return a = in<T>(); }
template<class T, class ... Args> inline void in(T &t, Args&... args) { in(t), in(args...); }template<class T> inline void out(T n) {if(n < 0) putc('-'), n = -n;if(n > 9) out(n / 10);putc(n % 10 + '0');
}template<class T1, class T2> T1 max(T1 a, T2 b) { return a > b ? a : a = b;}
template<class T1, class T2> T1 min(T1 a, T2 b) { return a < b ? a : a = b;}constexpr int N = 2e5 + 10;int c[N];
bool vis[N];
int sm[N];int n, q;int a[N], cnp, l[1000010], r[1000010];int pri[N];
bool is[1000010]; // 表示不是质数inline void line() { // 魔改线性筛板子for(int i = 2; i <= 1000000; i ++) {if(!is[i]) pri[++ cnp] = i;l[i] = cnp, r[i] = cnp + 1; // 记录第一个大于或小于等于的质数下标for(int j = 1; i * pri[j] <= 1000000 and j <= cnp; j ++) { is[pri[j] * i] = 1;if(i % pri[j] == 0) break;}}
}int fis[N];signed main() {#ifndef ONLINE_JUDGEfreopen("in.ru", "r", stdin);freopen("out.ru", "w", stdout);#endifin(n, q);for(int i = 1; i <= n; i ++) in(a[i]);for(int i = 1, x, k, op; i <= q; i ++) {in(op, k, x);x = (op == 1 ? -x : x);c[k] += x;if(!vis[k]) // 记录第一次for(int i = k; i <= n; i += k) !fis[i] ? fis[i] = op : 0; vis[k] = 1;}for(int i = 1; i <= n; i ++) if(c[i]) for(int j = i; j <= n; j += i) sm[j] += c[i]; // 求出总排名变换数line();is[1] = 1;  // 注意这三行特例r[1] = 1;for(int i = 1000000; !r[i]; i --) r[i] = 123123123;for(int i = 1; i <= n; i ++) {if(fis[i]) {int t;if(is[a[i]]) {if(fis[i] == 1) t = sm[i] + 1 + l[a[i]];if(fis[i] == 2) t = sm[i] - 1 + r[a[i]];}else t = sm[i] + l[a[i]];if(t <= 0) out(0);else if(t > cnp) out(1);else out(pri[t]);}else out(a[i]); e_;}
}   
// 星間~ 干渉~ 融解~ 輪迴~ 邂逅~ 再生~ ララバイ~
http://www.hskmm.com/?act=detail&tid=34469

相关文章:

  • 题解:P12003 在小小的奶龙山里面挖呀挖呀挖(加强版)
  • apisix升级完整流程
  • 10.11-10.18 一周总结
  • 10/19/2025 一周总结
  • 如何生成逼真的合成表格数据:独立采样与关联建模方法对比
  • winform+Task+async
  • AI元人文:跨学科视野下的人工智能伦理新范式
  • Rust 开发最佳实践(Rustlang Best Practices)
  • Why dont Japanese people reply to messages
  • 20232301郑好 实验二 后门原理与实践
  • 2025年复合钢丝网厂家推荐排行榜,昆山高精密网版,复合钢丝网公司精选!
  • 20232322 2025-2026-1 《网络与系统攻防技术》实验二实验报告
  • 消防局的设立
  • Python 潮流周刊#73:让我们对 PyPI 温柔一点,好吗?
  • 2025 年中国超声波流量计行业品牌全景分析报告:十大高性能品牌技术、性能与市场优势深度解析
  • 2025年精密弹簧厂家推荐排行榜,微型精密弹簧,不锈钢精密弹簧,高弹性精密弹簧公司推荐!
  • 2025网络推广服务推荐:云数智推,专业定制化营销解决方案!
  • React+Three.js 实现 Apple 2025 热成像 logo
  • 详细介绍:遥感目标检测数据集汇总,覆盖城市问题/工业安全/农业健康/室内场景……
  • 数据采集与融合作业1
  • CSP-S2023题解
  • 2025年氧化镁厂家最新推荐排行榜,活性氧化镁,肥料级氧化镁,优质供应与技术实力之选!
  • 运算符与自增自减
  • 2025年通风天窗/排烟天窗/通风气楼厂家最新推荐榜单,屋顶通风器/顺坡气楼/10A/1型/TC5A/TC12B/屋脊通风天窗公司推荐!
  • 使用autoDL gpu云服务器训练yolo的常用操作 - 东南西北风
  • 软件工程第三次作业-结对项目
  • with关键字
  • 2025精密球轴承优质厂家推荐:无锡雨露精工,国产高端定制首选!
  • 自定义注解
  • 2025 年电磁流量计最新推荐榜,聚焦企业技术实力与市场口碑深度解析