APTX部落

  • ACGN
  • Coding
  • WebServer
  • Daily
  • Share
  • Bangumi
APTX Blog
A Moe Blog Set Up By Mizuki
  1. 首页
  2. OI
  3. 正文

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

2018年8月8日 3023点热度 0人点赞 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);
}

 

标签: C/C++ C++ 拓展欧几里得 数论 模板 欧几里得 洛谷 算法 裴蜀定理
最后更新:2018年12月1日

神楽坂 みずき

萌萌萌,好萌!

点赞
< 上一篇
下一篇 >

文章评论

取消回复

神楽坂 みずき

萌萌萌,好萌!

搜索
最新 热点 随机
最新 热点 随机
私たちの居る理由 《サクラノ詩》VI 章 直哉与蓝对话 从《AMRITA》到《HELLO WORLD》── 野﨑まど世界观下的个体与世界的真实感 几种云端 VSCode/类 VSCode 方案对比与部署 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 React 配合后端热更新
家用无线组网最终方案 关于斐讯N1的救砖 C/C++Manacher算法(字符串判断回文串) 马拉车算法 模板 小米手环4NFC复制学校加密MifareClassic卡尝试与过程 0.99美元购买价值49刀的Google Home Mini Yandex Money塑料实体万事达借记卡评测
标签聚合
动漫 C++ C/C++ OI HTML 日常 洛谷 ST
分类
  • ACGN
  • Coding
  • Daily
  • OI
  • Share
  • WebServer

COPYRIGHT © 2022 APTX部落. ALL RIGHTS RESERVED.

Theme Kratos Made By Seaton Jiang