APTX博客

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

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

2018年8月8日 5132点热度 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 章 直哉与蓝对话
#动漫#路人女主的养成方法第二季 1080P 2019/10/03:MBTI & Politiscales调查问卷结果 #NOIP提高组#模板整理 C/C++Manacher算法(字符串判断回文串) 马拉车算法 模板 Summer Pockets REFLECTION BLUE 豪華限定版 早期予約色紙付き/通販・店舗対応版 寿屋:まちカドまぞく 千代田桃
标签聚合
ST 动漫 OI C++ C/C++ 洛谷 HTML 日常
分类
  • ACGN
  • Coding
  • Daily
  • DevOps
  • OI
  • Share

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

Theme Kratos Made By Seaton Jiang