Stein算法

前言

Stein算法‌‌是一种计算两个数最大公约数的算法,旨在改进在处理大整数时效率低下的问题。该算法通过减法和位移操作替代除法,提高了计算速度,尤其适用于硬件实现。‌

思路

具体步骤如下:

  1. 初始化‌:如果A=0,B是最大公约数,算法结束;如果B=0,A是最大公约数,算法结束。
  2. 迭代过程‌:
    • 如果A和B都是偶数,则同时除以2,并记录除去的因子2的乘积。
    • 如果一个是偶数一个是奇数,则将偶数除以2,奇数保持不变。
    • 如果A和B都是奇数,则用较大的数减去较小的数,然后取差与较小的数继续操作。
  3. 结束条件‌:当A和B相等时,停止迭代。此时,记录的2的乘积与A(或B)的最大公约数的乘积就是所求的最大公约数。

代码解决

#include <iostream>
using namespace std;
long long Highest_Common_Factor;
static void Stein(int a, int b) {long long n = a, m = b, c = 1;while (n == m)if (n % 2 == 0 && m % 2 == 0) {n /= 2;m /= 2;c *= 2;}elseif (n % 2 == 0)n /= 2;elseif (m % 2 == 0)m /= 2;elseif (n > m)n -= m;elsem -= n;Highest_Common_Factor = m * c;
}
int main() {int a, b;cin >> a >> b;Stein(a, b);cout << a << "和" << b << "的最大公因数是:" << Highest_Common_Factor << endl;return 0;
}

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

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

相关文章

懒饭 3.0.2 | 谷歌版纯净无广告教做菜软件

这款教做菜的软件是谷歌版&#xff0c;提供了一个纯净无广告的学习环境。即使没有会员&#xff0c;普通版也足够满足日常使用需求。软件内含分类和排行榜功能&#xff0c;支持搜索&#xff0c;教程形式多样&#xff0c;包括文字和视频&#xff0c;是学习烹饪技巧、追女朋友的好…

【数模学习笔记】插值算法和拟合算法

声明&#xff1a;以下笔记中的图片以及内容 均整理自“数学建模学习交流”清风老师的课程资料&#xff0c;仅用作学习交流使用 文章目录 插值算法定义三个类型插值举例插值多项式分段插值三角插值 一般插值多项式原理拉格朗日插值法龙格现象分段线性插值 牛顿插值法 Hermite埃尔…

计算机二级-Java系列(Java的特点)

java语言的特点 简单&#xff0c;面向对象&#xff0c;分布式&#xff0c;结构中立&#xff0c;可移植性&#xff0c;解释执行&#xff0c;健壮&#xff0c;安全&#xff0c;高性能&#xff0c;多线程和动态。 Java具有面向对象的三个基本特性为&#xff1a;封装&#xff0c;…

【Vue3 入门到实战】1. 创建Vue3工程

目录 ​编辑 1. 学习目标 2. 环境准备与初始化 3. 项目文件结构 4. 写一个简单的效果 5. 总结 1. 学习目标 (1) 掌握如何创建vue3项目。 (2) 了解项目中的文件的作用。 (3) 编辑App.vue文件&#xff0c;并写一个简单的效果。 2. 环境准备与初始化 (1) 安装 Node.js 和 …

vim使用指南

&#x1f3dd;️专栏&#xff1a;计算机操作系统 &#x1f305;主页&#xff1a;猫咪-9527-CSDN博客 “欲穷千里目&#xff0c;更上一层楼。会当凌绝顶&#xff0c;一览众山小。” 目录 一、Vim 的基本概念 1.Vim 的主要模式&#xff1a; 1.1普通模式 (Normal Mode) 1.2插入…

TCP-IP详解卷 TCP的超时与重传

TCP-IP详解卷1-21&#xff1a;TCP的超时与重传&#xff08;Timeout and Retransmission&#xff09; 一&#xff1a;介绍 1&#xff1a; 与数据链路层的ARQ协议相类似&#xff0c;TCP使用超时重发的重传机制。 即&#xff1a;TCP每发送一个报文段&#xff0c;就对此报文段设置…

卷积神经02-CUDA+Pytorch环境安装

卷积神经02-CUDAPytorch环境安装 在使用Python进行pytorch的使用过程中遇到各种各样的版本冲突问题&#xff0c;在此进行记录 0-核心知识脉络 1&#xff09;根据自己电脑的CUDA版本安装对应版本的Pytorch&#xff0c;充分的使用GPU性能2&#xff09;电脑要先安装【CUDA ToolKi…

【STM32-学习笔记-7-】USART串口通信

文章目录 USART串口通信Ⅰ、硬件电路Ⅱ、常见的电平标准Ⅲ、串口参数及时序Ⅳ、STM32的USART简介数据帧起始位侦测数据采样波特率发生器 Ⅴ、USART函数介绍Ⅵ、USART_InitTypeDef结构体参数1、USART_BaudRate2、USART_WordLength3、USART_StopBits4、USART_Parity5、USART_Mode…

为深度学习创建PyTorch张量 - 最佳选项

为深度学习创建PyTorch张量 - 最佳选项 正如我们所看到的&#xff0c;PyTorch张量是torch.Tensor​ PyTorch类的实例。张量的抽象概念与PyTorch张量之间的区别在于&#xff0c;PyTorch张量为我们提供了一个可以在代码中操作的具体实现。 在上一篇文章中&#xff0c;我们看到了…

RabbitMQ(四)

SpringBoot整合RabbitMQ SpringBoot整合1、生产者工程①创建module②配置POM③YAML④主启动类⑤测试程序 2、消费者工程①创建module②配置POM③YAML文件内配置&#xff1a; ④主启动类⑤监听器 3、RabbitListener注解属性对比①bindings属性②queues属性 SpringBoot整合 1、生…

项目练习:若依管理系统字典功能-Vue前端部分

文章目录 一、情景说明二、若依Vue相关代码及配置1、utils代码2、components组件3、api接口代码4、Vuex配置5、main.js配置 三、使用方法1、html部分2、js部分 一、情景说明 我们在做web系统的时候&#xff0c;肯定会遇到一些常量选择场景。 比如&#xff0c;性别&#xff1a;…

【 PID 算法 】PID 算法基础

一、简介 PID即&#xff1a;Proportional&#xff08;比例&#xff09;、Integral&#xff08;积分&#xff09;、Differential&#xff08;微分&#xff09;的缩写。也就是说&#xff0c;PID算法是结合这三种环节在一起的。粘一下百度百科中的东西吧。 顾名思义&#xff0c;…

微信小程序原生与 H5 交互方式

在微信小程序中&#xff0c;原生与 H5 页面&#xff08;即 WebView 页面&#xff09;之间的交互通常有以下几种方式&#xff1a; 1. 使用 postMessage 进行通信 微信小程序的 WebView 页面和原生小程序页面可以通过 postMessage 来进行数据传递。 WebView 页面向原生小程序发…

c++领域展开第十二幕——类和对象(STL简介——简单了解STL)超详细!!!!

文章目录 前言STL简介什么是STLSTL的版本STL的六大组件STL的重要性如何学习STL 总结 前言 上篇博客我们了解了初阶的模版函数&#xff0c;以及有关的一些使用方法。 今天我们来了解了解STL库的有关知识 跟我一起上车吧 STL简介 什么是STL STL&#xff1a;是C标准库的重要组成…

音频语言模型与多模态体系结构

音频语言模型与多模态体系结构 多模态模型正在创造语言、视觉和语音等以前独立的研究领域的协同效应。这些模型使用通用架构,将每种模式视为不同的“token”,使它们能够以一种与人类认知非常相似的方式联合建模和理解世界。 ​ ​可以将多模态分为两个主要领域:输入空间(…

HTML中最基本的东西

本文内容的标签&#xff0c;将是看懂HTML的最基本之基本 &#xff0c;是跟您在写文章时候一样内容。一般想掌握极其容易&#xff0c;但是也要懂得如何使用&#xff0c;过目不忘&#xff0c;为手熟尔。才是我们学习的最终目的。其实边看边敲都行&#xff0c;或者是边看边复制粘贴…

LVGL移植高通点阵字库GT30L24A3W

字库芯片: GT30L24A3W MCU:STM32F429 LVGL版本:V8.4 一、实现gt_read_data() 和 r_dat_bat() 请参考下面视频 如何在32位MCU上使用高通点阵字库_哔哩哔哩_bilibili 高通字库使用教程(1)硬件链接与注意事项部分_哔哩哔哩_bilibili 高通字库使用教程(2)SPI底层函数使用_哔哩…

计算机的错误计算(二百一十二)

摘要 利用两个大模型计算 实验表明&#xff0c;两个大模型均进行了中肯的分析。另外&#xff0c;其中一个大模型给出了 Python代码&#xff0c;运行后&#xff0c;结果中有7位错误数字&#xff1b;而一个大模型进行加减运算时出错。 例1. 计算 下面是与一个大模型的对话…

蓝桥与力扣刷题(709 转换成小写字母)

题目&#xff1a;给你一个字符串 s &#xff0c;将该字符串中的大写字母转换成相同的小写字母&#xff0c;返回新的字符串。 示例 1&#xff1a; 输入&#xff1a;s "Hello" 输出&#xff1a;"hello"示例 2&#xff1a; 输入&#xff1a;s "here…

9.7 visual studio 搭建yolov10的onnx的预测(c++)

1.环境配置 在进行onnx预测前&#xff0c;需要搭建的环境如下: 1.opencv环境的配置&#xff0c;可参考博客:9.2 c搭建opencv环境-CSDN博客 2.libtorch环境的配置&#xff0c;可参考博客&#xff1a;9.4 visualStudio 2022 配置 cuda 和 torch (c)-CSDN博客 3.cuda环境的配置…