第十四届蓝桥杯JavaA组省赛真题 - 互质数的个数

解题思路:

快速幂 + 欧拉函数

快速幂比较常见于数据较大的取模场景,欧拉函数感觉还是有点抽象

注意:

取模的时候就不要简写了,例如:res = res * a % mod;不要写成res *= a % mod;

import java.util.Scanner;public class Main {static int mod = 998244353;public static void main(String[] args) {Scanner sc = new Scanner(System.in);long a = sc.nextLong();long b = sc.nextLong();// 如果a等于1,则直接输出0,因为任何数的0次方都是1if (a == 1) System.out.println(0);// 初始化结果res为along res = a, x = a;// 循环,从2开始到x的平方根,检查x的因子for (int i = 2; i <= Math.sqrt(x); i++) {// 如果i是x的因子if (x % i == 0) {// 不断除以i,直到x不能被i整除while (x % i == 0) x /= i;// 根据欧拉定理,将res中所有i的因子替换为i-1res = res / i * (i - 1);}}// 如果x还有大于1的因子,重复上述操作if (x > 1) res = res / x * (x - 1);// 输出结果,为res乘以a的b-1次方,并对mod取模System.out.println(res * qmi(a, b - 1) % mod);}// 快速幂运算方法,用于计算a的b次方模mod的值private static long qmi(long a, long b) {long res = 1;while (b > 0) {if ((b % 2) == 1) res = res * a % mod;a = a * a % mod;b /= 2;}return res % mod;}
}

本文来自互联网用户投稿,该文观点仅代表作者本人,不代表本站立场。本站仅提供信息存储空间服务,不拥有所有权,不承担相关法律责任。如若转载,请注明出处:http://www.rhkb.cn/news/289655.html

如若内容造成侵权/违法违规/事实不符,请联系长河编程网进行投诉反馈email:809451989@qq.com,一经查实,立即删除!

相关文章

C++判断点是否在三角形内部

1.问题 判断点是否在三角形内部。 2.思路 计算向量AB和AP的叉积、向量BC和BP的叉积、向量CA和CP的叉积&#xff0c;如果所有的叉积符号相同&#xff0c;则点在三角形内部。 3.代码实现和注释 #include <iostream> #include <vector>// 计算两个二维向量的叉积 …

蚂蚁庄园今日答案

蚂蚁庄园是一款爱心公益游戏&#xff0c;用户可以通过喂养小鸡&#xff0c;产生鸡蛋&#xff0c;并通过捐赠鸡蛋参与公益项目。用户每日完成答题就可以领取鸡饲料&#xff0c;使用鸡饲料喂鸡之后&#xff0c;会可以获得鸡蛋&#xff0c;可以通过鸡蛋来进行爱心捐赠。其中&#…

基于JSP的辅导员工作管理系统

基于JSP的辅导员工作管理系统的设计与实现 摘要 在这个大时代信息化的背景之下&#xff0c;涌现了许多的信息化的管理模式&#xff0c;形成了这个大时代背景下的独有的管理的形式和独具特色的管理的类型和模式。其中就包括信息化的员工工作的管理模式。现在越来越多的人们接受…

电商打单ERP必备API列表-API调用指南

1、打开淘宝开放平台API文档&#xff0c;查看API参数。 2、选择需要的API&#xff0c;进行测试对接。注册账号获取APIkey 3、进入API测试页&#xff0c;开始测试taobao.custom custom-自定义API操作 公共参数 名称类型必须描述keyString是调用key&#xff08;必须以GET方…

Redis命令介绍

一、redis启动&#xff1a; 本地启动&#xff1a;redis-cli 远程启动&#xff1a;redis-cli -h host -p port -a password Redis 连接命令 1 AUTH password 验证密码是否正确 2 ECHO message 打印字符串 3 PING 查看服务是否运行 4 QUIT 关闭当前连接 5 SELECT index 切换…

如何用磁力仪探测管缆的位置和埋深?

不论是航空磁测&#xff0c;还是海洋磁测&#xff0c;都是直接测量磁场总强度T&#xff0c;而后以总磁异常ΔT成图。磁异常总强度Ta是磁场总强度T与正常场T0的矢量差&#xff0c;即&#xff1a; Ta&#xff1d; T&#xff0d; T0 根据参考文献1&#xff0c;2的推导&#xff0c…

c++红黑树

c红黑树 1. 红黑树的概念 红黑树&#xff0c;是一种二叉搜索树&#xff0c;但在每个结点上增加一个存储位表示结点的颜色&#xff0c;可以是Red或Black。通过对任何一条从根到叶子的路径上各个结点着色方式的限制&#xff0c;红黑树确保没有一条路径会比其他路径长出俩倍&…

Qt消息机制和事件

Qt消息机制和事件 Qt消息机制和事件--2 事件 事件&#xff08;event&#xff09;是由系统或者 Qt 本身在不同的时刻发出的。当用户按下鼠标、敲下键盘&#xff0c;或者是窗口需要重新绘制的时候&#xff0c;都会发出一个相应的事件。一些事件在对用户操作做出响应时发出&…

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现

基于JavaWEB SSM SpringBoot婚纱影楼摄影预约网站设计和实现 博主介绍&#xff1a;多年java开发经验&#xff0c;专注Java开发、定制、远程、文档编写指导等,csdn特邀作者、专注于Java技术领域 作者主页 央顺技术团队 Java毕设项目精品实战案例《1000套》 欢迎点赞 收藏 ⭐留言…

【Java程序设计】【C00415】基于(JavaWeb)Springboot的家教管理系统(含论文)

基于&#xff08;JavaWeb&#xff09;Springboot的家教管理系统&#xff08;含论文&#xff09; 项目简介项目获取开发环境项目技术运行截图 博主介绍&#xff1a;java高级开发&#xff0c;从事互联网行业六年&#xff0c;已经做了六年的毕业设计程序开发&#xff0c;开发过上千…

07、Lua 流程控制

Lua 流程控制 Lua 流程控制控制结构语句 Lua 流程控制 Lua编程语言流程控制语句通过程序设定一个或多个条件语句来设定。在条件为 true 时执行指定程序代码&#xff0c;在条件为 false 时执行其他指定代码。 以下是典型的流程控制流程图&#xff1a; 控制结构的条件表达式结…

VLAN详解

文章目录 VLANWhat-VLAN是什么When-VLAN是什么时候出现的Why-为什么需要VLANHow-VLAN是如何工作预备知识VLAN通信简述流程相同的VLAN间通信不同的VLAN间通信 VLAN的访问链接VLAN tagVLAN的接口类型和VLAN 标签的处理机制Access接口Trunk接口Hybrid接口 接口对比区别 VLAN间路由…

幻兽帕鲁服务器价格表_阿里云/腾讯云/京东云/华为云报价大全

2024年全网最全的幻兽帕鲁服务器租用价格表&#xff0c;阿里云幻兽帕鲁游戏服务器26元1个月、腾讯云32元一个月、京东云26元一个月、华为云24元1个月&#xff0c;阿腾云atengyun.com整理最新幻兽帕鲁专用4核16G、8核16G、8核32G游戏服务器租用价格表大全&#xff1a; 阿里云幻…

文献阅读笔记(Transformer)

文献阅读笔记&#xff08;Transformer&#xff09; 摘要Abstract1、文献阅读1.1 文献题目1.2 文献摘要1.3 研究背景1.4 模型架构1.4.1 Encoder-Decoder1.4.2 注意力机制1.4.3 多头注意力1.4.4 Position-wise Feed-Forward Networks1.4.5 Embeddings and Softmax1.4.6 Positiona…

使用Docker搭建YesPlayMusic网易云音乐播放器并发布至公网访问

目录 ⛳️推荐 1. 安装Docker 2. 本地安装部署YesPlayMusic 3. 部署公有云YesPlayMusic播放器 3.1 安装cpolar内网穿透 3.2 固定YesPlayMusic公网地址 ⛳️推荐 前些天发现了一个巨牛的人工智能学习网站&#xff0c;通俗易懂&#xff0c;风趣幽默&#xff0c;忍不住分享一…

PyQT5学习--新建窗体模板

目录 1 Dialog 2 Main Window 3 Widget Dialog 模板&#xff0c;基于 QDialog 类的窗体&#xff0c;具有一般对话框的特性&#xff0c;如可以模态显示、具有返回值等。 Main Window 模板&#xff0c;基于 QMainWindow 类的窗体&#xff0c;具有主窗口的特性&#xff0c;窗口…

Freemarker环境搭建快速入门

Freemarker环境搭建&快速入门 测试工程搭建快速入门Freemarker指令语法基础语法种类集合指令&#xff08;List和Map&#xff09;if指令运算符空置处理内建函数 输出静态化文件 测试工程搭建 创建一个freemarker-demo 的测试工程专门用于freemarker的功能测试与模板的测试。…

【数据结构】顺序表的实现——静态分配

&#x1f388;个人主页&#xff1a;豌豆射手^ &#x1f389;欢迎 &#x1f44d;点赞✍评论⭐收藏 &#x1f917;收录专栏&#xff1a;数据结构 &#x1f91d;希望本文对您有所裨益&#xff0c;如有不足之处&#xff0c;欢迎在评论区提出指正&#xff0c;让我们共同学习、交流进…

图片标注编辑平台搭建系列教程(3)——画布拖拽、缩放实现

简介 标注平台很关键的一点&#xff0c;对于整个图片为底图的画布&#xff0c;需要支持缩放、拖拽&#xff0c;并且无论画布位置在哪里&#xff0c;大小如何&#xff0c;所有绘制的点、线、面的坐标都是相对于图片左上角的&#xff0c;并且&#xff0c;拖拽、缩放&#xff0c;…

linux之进程

一、背景 冯.诺依曼体系结构 输入设备键盘、鼠标、摄像头、话筒、磁盘、网卡...输出设备显示器、声卡、磁盘、网卡...CPU运算器、控制器存储器一般就是内存 数据在计算机的体系结构进行流动&#xff0c;流动过程中&#xff0c;进行数据的加工处理&#xff0c;从一个设备到另一…