APTX博客

  • ACGN
  • Coding
  • DevOps
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By ミズキ
  1. 首页
  2. OI
  3. 正文

#C/C++#裴蜀定理(貝祖等式)

2018年8月8日 5076点热度 2人点赞 0条评论

裴蜀定理

在数论中,裴蜀等式是一个关于最大公约数(或最大公约式)的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀,说明了对任何整数a,b和m,关于未知数 x和y的线性丢番图方程(称为裴蜀等式):ax+by=m

有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解,每组解 x、y都称为裴蜀数,可用扩展欧几里得算法求得。

就是关于 x, y 的不定方程 ax + by =c  有整数解的充要条件是 gcd(a,b)∣c 。

题目见洛谷:P4549

模板

#include <cstdio>
#include <cmath>
#include <iostream>
#include <algorithm>
using namespace std;

int gcd(int ,int ); 


int main() {
	int t,ans = 0;
	cin >> t;
	for(int i = 1;i <= t;++i) {
		int tmp;
		scanf("%d",&tmp);
		if(tmp < 0) tmp = -tmp;
		ans = gcd(ans,tmp);
	}
	cout << ans << endl;
	return 0;
}

int gcd(int x,int y) {
	if(y == 0) return x;
	else return gcd(y,x % y);
}

 

本作品采用 知识共享署名-非商业性使用-相同方式共享 4.0 国际许可协议 进行许可
标签: C/C++ C++ 拓展欧几里得 数论 模板 欧几里得 洛谷 算法 裴蜀定理
最后更新:2018年12月1日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

razz evil exclaim smile redface biggrin eek confused idea lol mad twisted rolleyes wink cool arrow neutral cry mrgreen drooling persevering
取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
上岸 Star Divine 现代前端工程师发展方向不完全指北 站点域名变更通知 私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话
34.1G图片图包Ondrive/GDrive分流 使用Enlighter替换Crayon Syntax Highlighter插件 C++程序查看运行时间&&空间大小&&程序运行分析 C++中string类型字符串笔记 Manjaro 17.1.0+版本双系统安装后无引导的解决方法 关于斐讯N1刷机Linux(Armbian)及NAS两三事
标签聚合
C++ C/C++ 动漫 洛谷 ST HTML OI 日常
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

COPYRIGHT © 2017-2022 APTX博客. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang