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

CF2147G

CF2147G

困难数论题好窝心。

本文参考了官方题解。

假设 \(\gcd(a,m)=1\)\(a\not=1\) 的情况。

序列 \(b\) 的形式是 \(a^{a^N}\),要使得后面的 \(b_n=1 \bmod m\)\(ord_{m}(a)|a^N\),\(N\) 是一个极大的数。

那么要求对于 \(\forall p\mid ord_m(a),p|a\),其中 \(p\) 是质数。

\(rad(x)\)\(x\) 的所有质因子的乘积。

\(rad(ord_m(a))\mid a\)

这可以表明解是一个周期的:

\(a\) 为一个解,那么 \(a+ord_m(a)\times m\) 也为一个解。

因为 \(ord_m(a)\mid \phi(m)\),也就是说 \(m\phi(m)\) 是解的一个周期。

考虑统计 \(1\leq a<m, 0\leq \lambda<\phi(m),rad(ord_m(a))\mid a+\lambda m\) 的个数。

枚举阶 \(x=ord_m(a)\),记 \(cnt(x)\)\(1\leq a<m\) 中阶 为 \(x\) 的个数。

同时因为 \(\gcd(a,m)=1\),那么有 \(\gcd(x,m)=1\)

所以密度为:

\(\sum_{x\mid \phi(m),\gcd(x,m)=1}\frac{cnt(x)}{m}\times\frac{1}{rad(x)}\)

后面的 \(\frac{1}{rad(x)}\) 很好理解:

因为要求 \(rad(x)\mid a+\lambda m\),且 \(\gcd(rad(x),m)=1\),所以对于给定的 \(a\) 来说,每 \(rad(x)\)\(\lambda\) 就有一个解。

\(cnt(x)\) 是积性函数,是可以计算的,大概存在 \(O(d(m))\) 级别的解,因为存在多测,所以无法通过。

事实上:

\(\phi(x)\) 个值 \(a\),满足在模 \(x=p_i^{t_i}\) 的意义下,\(a\) 的阶是 \(p_i^{t_i}\)

又存在 \(ord_{xy}(a)=lcm(ord_{x}(a),ord_{y}(a))\),积性函数不言而喻。

考虑优化:

\(k\)\(q\) 的乘积,\(q_i\)\(\phi(m)\) 的质因数分解。

\(\sum_{x\mid \phi(m),rad(x)\mid k}cnt(x)=\sum_{d_1|q_1^{b_1},.....d_t|q_t^{b_t}}\prod \phi(d_i)\)

\(=\prod_{i}\sum_{d\mid q_i^{b_i}}\phi(d)\)

\(=\prod q_i^{b_i}\)

\(\sum_{x\mid \phi(m),rad(x)=k}cnt(x)=\sum_{I\subseteq |t|}(-1)^{t-|I|}\prod_{i\in I}q_{i}^{b_{i}}=\prod(q_{i}^{b_{i}}-1)\)

那么答案可以写成:

\(\frac{1}{m}\sum_{I\subseteq |t|}\sum_{rad(x)=\prod q_i}\frac{\prod (q_i^{b_i}-1)}{\prod q_i}\)

可以因式分解为:

\(\frac{1}{m}\prod (1+\frac{q_i^{b_i}-1}{q_i})\),这个可一通过质因数分解 \(m\)\(\phi(m)\) 计算。

注意到质因数的次数不能达到 \(m\) 对应质因数的次数,因为 \(\gcd(x,m)=1\)

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

相关文章:

  • 全栈开发者效率工具图谱:从IDE到云服务的最优组合 - 指南
  • 皇牌空战7豪华版DLC补丁
  • 基础语法
  • 遥感影像处理利器:PCL Geomatica 2018 功能与安装指南
  • EaseUS Partition Master 13.8 技术员版功能介绍与安装教程
  • 使用 Ansible 批量完成 CentOS 7 操作系统基础配置
  • BeanUtils中的copyProperties方法使用和分析
  • VUE + Nginx + Traefik 项目的发布与反向代理
  • CF *3500
  • CF *3400
  • 深度优先检索:单词搜索
  • WoTerm、WindTerm及putty的性能测试对比
  • CF333E Summer Earnings
  • 一文看懂Playwright MCP如何引爆AI智能体爆发
  • 从nano banana模型到更加真实的3D打印技术
  • 职业卡点怎么破?3个月私教服务助你升级技能与面试技巧
  • OI?原来这么简单-语法算法入门篇
  • 跨境tk避雷proxy-cheap代理服务商!!!
  • Rouyan:使用WPF/C#构建的基于LLM的快捷翻译小工具
  • BM25 关键词检索算法
  • 记录用户业务请求日志
  • [C++:类的默认成员函数——Lesson7.const成员函数] - 指南
  • 详细介绍:Xilinx系列FPGA实现12G-SDI音视频编解码,支持4K60帧分辨率,提供2套工程源码和技术支持
  • 使用 VMware Workstation 安装 CentOS-7 虚拟机
  • K12教育 和 STEAM教育
  • AT_arc167_c [ARC167C] MST on Line++
  • Lombok无法使用get set方法
  • redis的哈希扩容
  • vite tailwindcss配置
  • 在Vona ORM中实现多数据库/多数据源