题解 | #华华对月月的忠诚#

裴蜀定理

题目大意

给定 ，已知一种数列按照类斐波那契排列，如 + ， = ， = ，求

解法

裴蜀定理（或贝祖定理）得名于法国数学家艾蒂安·裴蜀，说明了对任何整数a、b和它们的最大公约数d，关于未知数x和y的线性不定方程（称为裴蜀等式）：若a,b是整数,且gcd(a,b)=d，那么对于任意的整数x,y,ax+by都一定是d的倍数，特别地，一定存在整数x,y，使ax+by=d成立。 它的一个重要推论是：a,b互质的充分必要条件是存在整数x,y使ax+by=1.

百度

所以可以根据以上信息可以写出代码：

//
#include <bits/stdc++.h>
#define ll long long
#define LM LLONG_MAX
#define IM INT_MAX
#define IMN INT_MIN
#define LMN LLONG_MIN
#define tr true
#define fa false 

using namespace std;

ll a, b;
string s;		//由于 n 有 10 ^ 10^ 5 长度，就用string存

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

int main(){
//  freopen(".in", "r", stdin);
//  freopen(".out", "w", stdout);
  cin >> a >> b >> s;
  cout << gcd(a, b);
  return 0;
}