原题
对于字符串 S 和 T，只有在 S = T + ... + T（T 与自身连接 1 次或多次）时，我们才认定 “T 能除尽 S”。
返回最长字符串 X，要求满足 X 能除尽 str1 且 X 能除尽 str2。
示例 1:
输入: str1 = "ABCABC", str2 = "ABC"
输出: "ABC"
示例 2:
输入: str1 = "ABABAB", str2 = "ABAB"
输出: "AB"
示例 3:
输入: str1 = "LEET", str2 = "CODE"
输出: ""
提示：
1 <= str1.length <= 10001 <= str2.length <= 1000str1[i] 和 str2[i] 为大写英文字母
解法
思想
这道题我之前想得很复杂！结果一看题解：卧槽还能这样。给大佬们跪了。
确实好久没接触这样的数学知识了：辗转相除法。
首先如果str1和str2有最大公因子，那么str1+str2就会等于str2+str1。
然后就是考虑怎么把最大公因子子字符串取出来，说实话辗转相除法我是没想到的，百度百科：
欧几里德算法又称辗转相除法，是指用于计算两个正整数a，b的最大公约数。应用领域有数学和计算机两个方面。计算公式gcd(a,b) = gcd(b,a mod b)。
这样求出两个字符串的长度的最大公因数，就是子字符串的长度，然后用substring取出来。
代码
class Solution {
public String gcdOfStrings(String str1, String str2) {
if(!(str1+str2).equals(str2+str1)) return "";
return str1.substring(0,gcd(str1.length(),str2.length()));
}
public int gcd(int x,int y){
return x%y==0?y:gcd(y,x%y);
}
}
原创文章，作者：彭晨涛，如若转载，请注明出处：https://www.codetool.top/article/leetcode1071-%e5%ad%97%e7%ac%a6%e4%b8%b2%e7%9a%84%e6%9c%80%e5%a4%a7%e5%85%ac%e5%9b%a0%e5%ad%90/
