首页 > 其他分享 >最大公约数学习笔记

最大公约数学习笔记

时间:2023-04-26 21:22:57浏览次数:48  
标签:return gcd int ll 笔记 else 学习 最大公约数 bigint

一、定义

因数/约数:给定一个正整数 \(x\),\(x\) 的因数/约数就是所有满足 \(x\) 是 \(y\) 的正整数倍的 \(y\)。

最大公因数/最大公约数:给定两个正整数 \(a\),\(b\),求一个最大的正整数数 \(x\),使得它同时是 \(a\) 和 \(b\) 的因数。

一般在 OI 中记为 \((a,b)=x\),在数学上记为 \(\gcd(a,b)=x\)。

二、求法

1. 辗转相减法

怎么求?假设 \(a>b\),\(\gcd(a,b)=x\),那么发现由于 \(a\) 和 \(b\) 都是 \(x\) 的整数倍,所以 \(a-b\) 是 \(x\) 的整数倍,\(\gcd(a-b,b)\) 依然是 \(x\) 的倍数。所以 \(\gcd(a,b)|\gcd(a-b,b)\)。

反过来,假设 \(\gcd(a-b,b)=y\),那么我们发现 \(b\) 是 \(y\) 的整数倍,并且 \(a=(a-b)+b\) 是 \(y\) 的倍数,所以 \(\gcd(a,b)\) 是 \(y\) 的的倍数。所以 \(\gcd(a-b,b)|\gcd(a,b)\)。

所以 \(\gcd(a,b)=\gcd(a-b,b)\)。

反复用大的减去小的,在有限次操作后一定有一个数变为 \(0\),因为一开始 \(a+b\) 有限并且在 \(a,b>0\) 时 \(a+b\) 严格递减。

那么此时另一个数不为 \(0\),就是原来的 \(\gcd(a,b)\)。

时间复杂度 \(O(\max\{a,b\})\)。

这是因为我们可以令 \(b=1\),那么就需要跑 \(a\) 次。

ll gcd(ll a,ll b){
	if(!b)return a;
	else return gcd(b,a-b);
}

2. 辗转相除法(欧几里得算法)

这样要花费很久,所以可以将减换为取模。

ll gcd(ll a,ll b){
	if(!b)return a;
	else return gcd(b,a%b);
}

当然,压压行。

ll gcd(ll a,ll b){
	return (!b)?a:gcd(b,a%b);
}

这样的时间复杂度是 \(O(\log\max\{a,b\})\)。

3. 辗转相减法的优化

如果 \(a,b\le 10^{10000}\),该怎么办?我们发现,高精度除法常数较大而且非常难写。

此时我们可以考虑如下算法:假设 \(a>b\),针对 \(a,b\) 分类,

  1. \(a,b\) 中有一个是 2 的倍数,那么除以 2 就可以了。

  2. \(a,b\) 都是 2 的倍数,那么全部除以 2,把答案乘 2 就可以了。

  3. \(a,b\) 中没有 2 的倍数,那么返回 \(\gcd(a,a-b)\) 就可以了。

容易知道每出现一次 3,就会出现 1、2 中的一种情况,因为奇数减奇数是偶数。所以时间复杂度是 \(O(\log\max\{a,b\})\)。压位高精可以有效减少常数。

P2152 [SDOI2009] SuperGCD

注意这一题要高精,总时间复杂度 \(O(\log^2\max\{a,b\})\)

#include<bits/stdc++.h>
using namespace std;
typedef long long ll;
struct bigint{int l,a[1210];}p,q,tmp;
int cnt=0,bs=1000000000;//记录 2 的次数,压位高精 
inline void print(bigint x){
	for(int i=x.l-1;i>=0;i--){
		if(i!=x.l-1){
			if(x.a[i]<=100000000)putchar(48);
			if(x.a[i]<=10000000)putchar(48);
			if(x.a[i]<=1000000)putchar(48);
			if(x.a[i]<=100000)putchar(48);
			if(x.a[i]<=10000)putchar(48);
			if(x.a[i]<=1000)putchar(48);
			if(x.a[i]<=100)putchar(48);
			if(x.a[i]<=10)putchar(48);
		}
		cout<<x.a[i];
	}
	putchar(10);
}
inline bigint read(){
	bigint r;r.l=0;memset(r.a,0,sizeof(r.a));
	string s;cin>>s;int x=0,n=s.size(),c=n;
	for(c=n;c>=9;c-=9){
		for(int i=-9;i<0;i++)x=(x<<3)+(x<<1)+(s[c+i]^48);
		r.a[r.l++]=x,x=0;
	}
	if(c){
		for(int i=0;i<c;i++)x=(x<<3)+(x<<1)+(s[i]^48);
		r.a[r.l++]=x;
	}
	return r;
}
inline bool cmp(bigint x,bigint y){
	if(x.l^y.l)return x.l>y.l;
	for(int i=x.l-1;i>=0;i--)
		if(x.a[i]^y.a[i])return x.a[i]>y.a[i];
	return 0;
}
inline bigint sub(bigint x,bigint y){
	for(int i=x.l-1;i>=0;i--)x.a[i]-=y.a[i];
	for(int i=0;i<x.l;i++)
		if(x.a[i]<0)x.a[i]+=bs,x.a[i+1]--;
	if(!x.a[x.l-1])x.l--;
	return x;
}
inline bigint div2(bigint x){
	for(int i=0;i<x.l;i++)x.a[i]=(x.a[i+1]&1)*bs/2+x.a[i]/2;
	if(!x.a[x.l-1])x.l--;
	return x;
}
inline bigint mul2(bigint x){
	for(int i=0;i<x.l;i++)x.a[i]<<=1;
	for(int i=0;i<x.l;i++)
		if(x.a[i]>=bs)x.a[i]-=bs,x.a[i+1]++;
	if(x.a[x.l])x.l++;
	return x;
}
int main(){
	p=read();q=read();
	if(cmp(q,p))tmp=p,p=q,q=tmp;//保证 p>q 
	while(q.l){
		if((p.a[0]%2==0)&&(q.a[0]%2==0)){
			cnt++;
			p=div2(p);
			q=div2(q);
		}else if(p.a[0]%2==0)p=div2(p);
		else if(q.a[0]%2==0)q=div2(q);
		else p=sub(p,q);
		if(cmp(q,p))tmp=p,p=q,q=tmp;
	}
	while(cnt--)p=mul2(p);
	print(p);
	return 0;
}

标签:return,gcd,int,ll,笔记,else,学习,最大公约数,bigint
From: https://www.cnblogs.com/qwq-qaq-tat/p/17356666.html

相关文章

  • 构建之法阅读笔记与感悟06
    9.1PM是啥软件团队里除了能写代码、测试代码和画图做设计的成员,还有一类角色,不做上面这些事情但也很重要,我们叫他们项目经理——PMPM的M就是Manager,但是P有这几种:ProductManager、ProjectManager、ProgramManager,在不同的行业和公司,他们的作用各不相同。接下来介绍的是项目经......
  • 华为HCIP学习清单
    华为HCIP学习清单本篇博客用于汇总本人对于华为HCIP-Datacom方向的学习笔记,便于索引.笔记HCIP-ICT实战进阶01-OSPF各类LSA介绍及分析HCIP-ICT实战进阶02-OSPF特殊区域及其他特性HCIP-ICT实战进阶03-OSPF高级特性HCIP-ICT实战进阶04-ISIS原理与配置HCIP-ICT实战进阶05-路......
  • 利用pytorch深度学习框架验证骰子的合格性
    利用pytorch深度学习框架验证骰子的合格性骰子生产的合格性可以用概率来表达,比如每个面出现的概率大概都是1/6。importtorchfromd2limporttorchasd2lfromtorch.distributionsimportmultinomial#多次扔骰子出现每个面的概率服从多项式分布fair_probs=torch.ones(......
  • Django笔记三十一之全局异常处理
    本文首发于公众号:Hunter后端原文链接:Django笔记三十一之全局异常处理这一篇笔记介绍Django的全局异常处理。当我们在处理一个request请求时,会尽可能的对接口数据的格式,内部调用的函数做一些异常处理,但可能还是会有一些意想不到的漏网之鱼,造成程序的异常导致不能正常运行,......
  • Linux笔记
    Linux注:笔记中带有特殊标识,特殊标识仅为作者自己设立,起提醒作用枫染:主要是标识额外的其他命令,或补充命令幻舞:主要是标识命令的其他用法,多用法,或选项寒星:主要是标识快捷方式和键盘操作落霞:主要是标识其他操作或危险命令操作Linux用户Linux的用户有三种:root 普通用户 系统......
  • 【学习笔记】拓展中国剩余定理
    若干方程组:\(\begin{cases}x\equivc_1\quad(\modp_1)\\x\equivc_2\quad(\modp_2)\\···\\x\equivc_m\quad(\modp_m)\end{cases}\)求x但不保证p互质。采用两两方程合并的形式。\(\begin{cases}x\equivc_1\quad(\modp_1)\\x\equivc_2\quad(\modp_2)\......
  • 【专题】2022年中国企业数字化学习行业研究报告PDF合集分享(附原数据表)
    报告链接:http://tecdat.cn/?p=32263原文出处:拓端数据公众号多变,不确定性,复杂,模糊不清的新业务图景,加快了公司人才发展模式的数字化转变;疫情冲击离线运输与公司现金流量,消费者支出减少,机构表现受压,数字化学习突破;行业数字化水平不断提高,商业体系和学习体系之间的关联性不断加强,企......
  • Webserver学习笔记
    前言Webserver这个东西真的恶心的一批,很难自学,但是网上又没有现成的教程(谁没事写一个Webserver啊)。这篇文章主要提供Webserver的基本框架的思路,毕竟网站基本框架相同无疑于抄袭,SSD可以先走了。正文准备本篇博客的Webserver基于SOCKET实现,这样只是为了追求底层,相对......
  • CVPR'23|向CLIP学习预训练跨模态!简单高效的零样本参考图像分割方法
    前言 本文提出了一种zero-shot的Referringimagesegmentation方法,该方法利用了来自CLIP的pre-train的跨模态知识。所提方法的性能明显优于所有基线方法和监督较弱的方法。本文转载自极市平台作者|CV开发者都爱看的仅用于学术分享,若侵权请联系删除欢迎关注公众号CV技术指南......
  • 深度学习网络fine-tune原理研究 - 以卷积神经网络为例
    一、什么是预训练模型(pre-trainedmodel)预训练模型就是已经用数据集训练好了的模型,这里的数据集一般指大型数据集。比如VGG16/19ResnetImagenetCOCO正常情况下,在图像识别任务中常用的VGG16/19等网络是他人调试好的优秀网络,我们无需再修改其网络结构。参考资料:https://z......