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

20251023 正睿二十连测

B

时间:看了题解后花了 \(30\) 多分钟吧。

给定 \(n\) 对数 \((a_i, b_i)\) 以及 \(T\) 组询问,每组询问给定 \((x, y)\),问有多少对给定的数能通过对 \((x, y)\) 进行若干次以下两种操作得到?

  • \((x, y) \leftarrow (x, x + y)\)
  • \((x, y) \leftarrow (x + y, y)\)

\(n, T \le 10^5, 1 \le a_i, b_i, x, y \le 10^{18}\)

正着做似乎毫无前途,至少我考时打了一个小时表毫无规律,它进行不同的操作后也几乎不会到达重复的状态,然后就寄了。

看了一眼题解,告诉我们要倒着做,然后几乎就秒会了。

首先操作肯定是可逆的,无非是 \((x, y) \leftarrow (x - y, y)\)\((x, y) \leftarrow (x, y - x)\)。但是倒着做有什么好处呢?

凭借我们惊人的注意力:\(a_i, b_i, x, y\) 都是大于 \(0\) 的,而一个带有负数的对 \((-p, q)\) 无论怎么操作都至少还有一个负数,所以减的时候一定时大的减小的,操作时唯一确定的,而不是有两种。

而这玩意很像辗转相除法,只不过是减法。但是一个个减肯定会超时,还是只能按照辗转相除法做。

不妨设 \(a_i > b_i, k = a_i \% b_i\),则 \((k, b_i), (k + y, b_i) , \dots , (a_i, b_i)\) 都是可以的。我们可以把这些数概括成一个三元组 \((b_i, k, a_i)\) 表示对于询问的 \((x, y)\),若 \(y = b_i, x \% y = k, x \le a_i\) \((x, y)\) 就是那一串数中的一个。

那么将所有 \(n \log V\) 个三元组排序,然后查询时二分出一段区间即可得到答案。对于 \(a_i < b_i\) 的情况同样的做一遍即可,两边互不影响。

时间复杂度:\(O(n \log V \log n)\),注意下常数还是能过的。

似乎 \((k, b_i)\) 到辗转相除一次时会再算一次,不过将 \(y \le b_i\) 改成 \(y \le b_i - x\) 就可以了。

这个题难点就是要想到倒着做,这样操作时固定的,然后就不难了。(脑瘫了,一直想正着做。)

http://www.hskmm.com/?act=detail&tid=37630

相关文章:

  • 1019:浮点数向零舍入(分正负取整)
  • 二分图/忆re.
  • 《IDEA 2025长效采用配置指南:有效期配置至2099年实战之JetBrains全家桶有效》​
  • ZKW线段树
  •  pytorch 66页实验题
  • Visual Studio 插件 - 喝水提醒 - 指南
  • JAVA 排序用法
  • 10/23
  • 10月23日
  • 第3天(中等题+简单题 数组、滑动窗口)
  • esp32-usb-jtag 调试踩坑
  • MySQLDay3
  • 飞牛OS通过docker部署SillyTavern酒馆
  • MySQL主从同步读写分离
  • ollama v0.12.2 版本更新详解:Qwen3 架构协助、Multi-Regex 分词器、新引擎前后缀匹配等功能升级
  • AI股票预测分析报告 - 2025年10月23日 20:26
  • 软件包管理
  • nginx反向代理测试搭建
  • 基础概念
  • .NET Core报错克服【无废话上操作】
  • 题解:P11831 [省选联考 2025] 追忆
  • 2025-10-23 MX-S 模拟赛 赛后总结【MX】
  • PCL1.12 解决memory.h中EIGEN处中断问题
  • 完整教程:状态管理库 Zustand 的接入流程与注意点
  • 20251023
  • Java常用机制 - SPI机制详解
  • 塔吊施工环境与附属设施监测!思通数科 AI 卫士筑牢全场景安全防线
  • 采用opencv来识别信用卡的号码
  • 网络设备
  • 第二十二篇