裴蜀定理
在数论中，裴蜀等式是一个关于最大公约数（或最大公约式）的定理。裴蜀定理得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a,b和m，关于未知数 x和y的线性丢番图方程（称为裴蜀等式）：ax+by=m
有整数解时当且仅当m是 a及b的最大公约数d的倍数。裴蜀等式有解时必然有无穷多个整数解，每组解 x、y都称为裴蜀数，可用扩展欧几里得算法求得。
就是关于 x, 的不定方程 ax + by 有整数解的充要条件是 g 。
题目见洛谷:P4549
模板
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 |
#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); } |
