扩展欧几里德_euclid ccc-程序员宅基地

技术标签: 模板  

typedef long long LL;
//扩展欧几里德递归实现 版本1
void exgcd(LL a, LL b, LL& g, LL& x, LL& y)
{
    if (!b) g = a, x = 1, y = 0;
    else exgcd(b, a%b, g, y, x), y -= x * (a / b);
}

//扩展欧几里德递归实现  版本2
//求(x,y),满足 a*x+b*y==1。返回值r即gcd(a,b)的值
int exgcd(int a, int b, int &x, int &y)
{
    if(b == 0)
    {
        x = 1;
        y = 0;
        return a;
    }
    int r = exgcd(b, a%b, x, y);
    int t = y;
    y = x - (a/b) * y;
    x = t;
    return r;
}

//扩展欧几里德的非递归实现,返回值表示gcd(m,n); 
int exgcd(int m, int n, int &x, int &y) {
    if (n == 0) {
        x = 1; y = 0;
        return m;
    }
    int a, a1, b, b1, c, d, q, r, t;
    a1 = b = 1;
    a = b1 = 0;
    c = m; d = n;

    q = c/d; r = c%d;
    while (r) {
        c = d;
        d = r;
        t = a1;
        a1 = a;
        a = t - q * a;
        t = b1;
        b1 = b;
        b = t - q * b;

        q = c/d;
        r = c%d;
    }
    x = a; y = b;
    return d;
} 
版权声明:本文为博主原创文章,遵循 CC 4.0 BY-SA 版权协议,转载请附上原文出处链接和本声明。
本文链接:https://blog.csdn.net/CharlieHuu/article/details/81672198

智能推荐

Postgresql/PgSQL如何高效的快速插入记录_postgresql 插入性能-程序员宅基地

文章浏览阅读1k次。前两天,需要给构建的测试库灌入测试数据,发现Insert性能非常差。_postgresql 插入性能

Pycharm中英文语言切换以及背景色更改问题_更改pycharm语言-程序员宅基地

文章浏览阅读1w次,点赞10次,收藏25次。项目场景:提示:这里简述项目相关背景:最近开始接触python,用到pycharm,软件的安装没什么问题,就一些基本设置写一下做个记录,持续更新自己遇到的一些问题或者值得分享的应用。问题描述提示:这里描述项目中遇到的问题:今天是两个小设置,一个是改成中文系统,一个是背景色的更改。都不难,大家可参考看看。解决方案:提示:这里填写该问题的具体解决方案:一、语言的更改第一步:打开pycharm,file中找到settings或者快捷方式“Ctrl+Art+S”第二步:在settings找_更改pycharm语言

MinGW-w64下载资源整理_x86_64-5.4.0-release-posix-sjlj-rt_v5-rev0.7z-程序员宅基地

文章浏览阅读160次。百度网盘链接:https://pan.baidu.com/s/1aaCnHpprpRLVl16mpQKxhw_x86_64-5.4.0-release-posix-sjlj-rt_v5-rev0.7z

java程序语言设计-程序员宅基地

文章浏览阅读889次,点赞19次,收藏12次。Java是美国Sun Microsystems公司于1995年5月正式发布的程序设计语言,它是前身是公司为智能消费类家用电器(如:电视机、电话、闹钟、烤面包机)研究而开发的,直到1993年Web开始在Internet上盛行,开发小组试着将这一技术转移到Web网络上,并获得了空前的成功。

【SQLserver】常见问题和解决方案_sql server常见问题csdn-程序员宅基地

文章浏览阅读928次。sqlserver创建问题查询和解决方案_sql server常见问题csdn

【198】Java8编写Main程序场景下引入log4j2的例子-程序员宅基地

文章浏览阅读970次,点赞16次,收藏19次。有些情况下,需要程序员编写非服务器程序,或者编写不使用 Springboot 框架的程序。这个时候如果需要生成日志,就要采用本文的方法来引入 log4j2 。本文的例子还涉及了在程序打包的时候,如何处理依赖jar包的问题。

随便推点

你知道微视背后的视频特效技术是怎样做出来的吗?-程序员宅基地

文章浏览阅读304次。欢迎大家前往腾讯云+社区,获取更多腾讯海量技术实践干货哦~本文由腾讯视频云终端团队发表于云+社区专栏常青, 2008 年毕业加入腾讯,一直从事客户端研发相关工作,先后参与过 PC QQ、手机QQ、QQ物联 等产品项目,目前在腾讯视频云团队负责音视频终端解决方案的优化和落地工作,帮助客户在可控的研发成本投入之下,获得业内一流的音视频解决方案,目前我们的产品线包括:互动直播、点播、短视频、实..._电影特效是基于opengl吗

【基于springboot宠物咖啡馆平台的毕业设计】-程序员宅基地

文章浏览阅读691次,点赞14次,收藏28次。博主介绍:全网粉丝15W+,CSDN特邀作者、211毕业、高级全栈开发程序员、大厂多年工作经验、码云/掘金/华为云/阿里云/InfoQ/StackOverflow/github等平台优质作者、专注于Java、小程序技术领域和毕业项目实战,以及程序定制化开发、全栈讲解、就业辅导精彩专栏 推荐订阅2023-2024年最值得选的微信小程序毕业设计选题大全:100个热门选题推荐2023-2024年最值得选的Java毕业设计选题大全:500个热门选题推荐Java精品实战案例《500套》

学术搜索引擎大全(转自:http://scienceroom.net/scholar-search-engines)_0mag.net-程序员宅基地

文章浏览阅读2.8k次。学术搜索引擎–综合性Google学术搜索Scirus学术搜索BASE搜索Vascoda搜索万方数据ilib百度文档搜索OJOSEInfomineOA图书馆(开放存取搜索)PDF搜索引擎SciSeekSoopleSocolar(开放存取检索)深度搜PPT(幻灯片)搜索指针网学术搜索OAIster_0mag.net

入坑程序员,过来人给的一些小建议......-程序员宅基地

文章浏览阅读152次。总结1、尽量进大公司,不能进的采取『曲线救国』的策略,边学习边准备。2、选个有成长性的公司,钱不钱刚开始不重要。3、工作中,主动学习,自我反省,学会总结,经常复盘。4、不管胃口好不好,遇..._入坑程序员

SqlServer函数大全二十三:LEFT(取左边指定个数的字符)函数_sqlserver left-程序员宅基地

文章浏览阅读558次,点赞14次,收藏8次。但是,如果你是在使用C#作为ASP.NET应用程序的后端语言,并且你想要实现类似于SQL Server中。这样,当用户请求这个视图时,他们会看到字符串"abc"作为原始字符串"abcdefg"的左侧部分。函数的功能(即获取字符串的左侧部分),你可以使用C#的字符串索引和长度特性来实现。方法用于从字符串的起始位置(索引0)开始提取指定长度(这里是3)的子字符串。函数用于返回字符串的左侧指定数量的字符。在ASP.NET中,并没有一个直接名为。在SQL Server中,在C#中,你可以通过索引和。_sqlserver left

STM32F407跑马灯实验-库函数1-程序员宅基地

文章浏览阅读386次,点赞10次,收藏9次。有main.c,stm32f4xx_rcc.c,stm32f4xx_gpio.c,stm32f4xx_gpio.h,usart.c,delay.c,外设需要写HARDWARE一个文件夹,在写一个LED文件夹,进去在写led.h和led.c文档。

推荐文章

热门文章

相关标签