尧图网络 高端网站定制 · 原创设计
免费咨询热线
400-888-6620
免费获取方案
UVa 13197 Cuberoot This
题目描述给定一个素数ppp和一个常数0ap0 a p0ap。求所有满足x3≡a(modp)x^3 \equiv a \pmod px3≡a(modp)的xxx。输入格式每行一组数据最多100010001000组包含两个整数aaa和ppp其中ppp是素数且p1000p 1000p1000。输入直到文件结束。输出格式对于每组数据按升序输出所有满足条件的xxx0≤xp0 \le x p0≤xp每个数之间用一个空格隔开输出占一行。如果没有解则输出一个空行。样例输入2 31输出4 7 20题目分析本题要求解模素数ppp下的立方同余方程x3≡a(modp)x^3 \equiv a \pmod px3≡a(modp)。由于ppp是素数且p1000p 1000p1000数据范围非常小可以直接采用暴力枚举的方法遍历所有可能的xxx值000到p−1p-1p−1验证是否满足同余式。暴力枚举的时间复杂度为O(p)O(p)O(p)而每组输入的ppp不超过100010001000最多100010001000组输入总计算量不超过10610^6106次模乘运算在C\texttt{C}C中可以在极短时间内完成。因此本题不需要利用数论中的原根、离散对数等高级理论简单的枚举即可通过。解题思路对于每一组输入(a,p)(a, p)(a,p)执行以下步骤初始化一个布尔标记用于控制输出时数字之间的空格格式。使用循环变量xxx从000遍历到p−1p-1p−1。计算x3 mod px^3 \bmod px3modp由于p1000p 1000p1000可直接使用646464位整数如long long\texttt{long long}long long避免溢出不过实际上100031091000^3 10^910003109仍在323232位整数范围内但为了安全仍用long long\texttt{long long}long long。若计算结果等于aaa则输出xxx并在后续输出前添加空格分隔。遍历结束后输出换行。若没有任何xxx满足条件则直接输出空行。由于ppp是素数但本算法并不依赖该性质对于任意正整数ppp同样有效只要aaa在合理范围内因此具有通用性。代码实现// Cuberoot This// UVa ID: 13197// Verdict: Accepted// Submission Date: 2026-06-24// UVa Run Time: 0.010s//// 版权所有C2026邱秋。metaphysis # yeah dot net#includebits/stdc.husingnamespacestd;intmain(){inta,p;while(cinap){boolfirsttrue;for(intx0;xp;x){if((1LL*x*x*x)%pa){if(!first)cout ;coutx;firstfalse;}}cout\n;}return0;}总结本题核心在于观察到数据范围极小从而选择最直接的暴力枚举解法无需复杂数论知识。枚举所有xxx并检验同余式代码简洁易于实现。输出格式控制是本题的一个小细节需要注意多个答案之间的空格分隔以及无解时的空行输出。该解法的时间复杂度为O(∑p)O(\sum p)O(∑p)空间复杂度为O(1)O(1)O(1)在给定限制下完全可行。当ppp较大时需要利用数论性质如三次剩余优化但本题并无此要求。
RELATED

相关推荐

IDEA内置终端npm -v报错?根因排查与修复指南

IDEA内置终端npm -v报错?根因排查与修复指南

我印象很深,有一次某前端同学把 IDEA 内置终端打开,敲npm -v,终端直接甩了两行:npm 不是内部或外部命令,也不是可运行的程序或批处理文件。他转头在 Windows 的 cmd 里试了一下,同一个命令,好端…

📅 2026/10/10 5:49:26
PCA9422+PIC32MX构建可编程电源管理子系统

PCA9422+PIC32MX构建可编程电源管理子系统

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📅 2026/10/10 5:49:26
CS自学指南:20+ 方向选课地图,零基础 3 步定好学习路线

CS自学指南:20+ 方向选课地图,零基础 3 步定好学习路线

CS自学指南:20 方向选课地图,零基础 3 步定好学习路线 【免费下载链接】cs-self-learning 计算机自学指南 项目地址: https://gitcode.com/GitHub_Trending/cs/cs-self-learning 一堆上百门公开课,挑花眼怎么办?CS自学指南…

📅 2026/10/10 5:49:26
MORE NEWS

更多资讯

📰

PS5游戏元数据解析工具开发指南

我无法根据当前输入生成符合要求的博文。原因如下:项目标题“AnyPS5”缺乏明确指向性,未说明是硬件改装、模拟器开发、游戏兼容层、跨平台移植方案,还是其他技术方向;项目正文为空,无任何功能描述、技术目标、实现方式…

📰

给电脑装个“嘴“,AI才真正学会用电脑

你有没有想过一个问题:如果让你远程操作一台电脑,帮别人改一份Excel表格里几百行数据的格式,你会怎么做?大概率你不会一个一个单元格去点右键改字体,你会打开一个脚本,写几行代码,唰地一下全改完…

📰

基于PCA9422与STM32F215ZG的电池供电电源管理方案实战

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📰

C# 连接 MQTT 服务器实战:MQTTnet 选型、发布订阅与断线重连

简介:这份资源是一套基于C#语言实现MQTT协议通信的完整项目源码,面向物联网开发初学者与需要搭建设备上云监控系统的C#开发者。项目围绕MQTT客户端与服务器的连接展开,涵盖定时发布车间信息、响应服务器请求、机床数据定时采集与界面实时刷新…

📰

工业互联网数字化中台:从设备接入到数据服务的架构选型与避坑指南

/* MD / 富文本中的 .toc(含博客园搬家等嵌套结构);.toc-box 在侧栏,不受影响 */#content_views .toc,/* 编辑器常在目录前后插入空 p(:empty 仍占 20px),一并去掉避免顶空隙 */#content_views.markdown_views > p:empty:has(+ .toc),#content_views.markdown_views …

📰

百度街景API试用申请全攻略:从注册到开通的详细步骤(适合学术研究)

百度街景API试用申请全攻略:从注册到开通的详细步骤(适合学术研究) 引言:为什么我们需要百度街景API? 作为一名从事城市空间智能研究的研究生,我经常需要获取城市街景影像来分析街道绿化、行道树种类、树高…

TODAY

今日更新

THIS WEEK

本周精选

THIS MONTH

本月热门

读完文章,想聊聊您的网站?

告诉我们您的行业与需求,资深顾问一对一梳理方案与报价,全程免费。

📞 💬