今天做了一道题，需要求最大公因数，已经完全把辗转相除法忘记了，特此记录
辗转相除法
辗转相除法，也叫欧几里得算法，用于计算两个正整数a，b的最大公约数，计算公式gcd(a,b) = gcd(b,a mod b)。划重点，辗转相除法是世界上最早的算法，诞生于公元前300年。凉凉，我可以回到2320年前重新做人了
例子源于百度百科
求1997和615的最大公约数
1997 / 615 = 3 (余 152)
615 / 152 = 4(余7)
152 / 7 = 21(余5)
7 / 5 = 1 (余2)
5 / 2 = 2 (余1)
2 / 1 = 2 (余0)
至此余数为0，最大公约数为1
以除数和余数反复做除法运算，当余数为 0 时，取当前算式除数为最大公约数
欧几里得算法python实现
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
做到的题目
求两个字符串的最大公因串
题目源于leetcode 1071. 字符串的最大公因子
思路：
- 假设存在一个公因串S，那么len(S)显然是两个字符串长度的公因数。设两个字符串长度的最大公因数为N，显然有N是len(S)的倍数。因此，公因串S可以不断复制至长度到达N，形成新串S'，S'即为所求
- 那么，我们直接求出最大公因数N，取出该长度的前缀串，判断一下它是否能经过若干次拼接得到 str1 和 str2 即可
class Solution:
def gcdOfStrings(self, str1: str, str2: str) -> str:
def gcd(a, b):
if b == 0:
return a
return gcd(b, a % b)
len1 = len(str1)
len2 = len(str2)
n = gcd(len1, len2)
if str1[:n] * (len1 // n) == str1 and str1[:n] * (len2 // n) == str2:
return str1[:n]
return ''
