1071. 字符串的最大公因子
1071. Greatest Common Divisor of Strings
For two strings s and t, we say “t divides s” if and only if s = t + … + t (i.e., t is concatenated with itself one or more times).
Given two strings str1 and str2, return the largest string x such that x divides both str1 and str2.
對於字串 s 和 t，只有在 s = t + … + t（t 自身連接 1 次或多次）時，我們才認定「t 能除盡 s」。
給定兩個字串 str1 和 str2 。傳回最後一個字串 x，要求滿足 x 能除盡 str1 且 x 能除盡 str2 。
範例1：
1
2
輸入：str1 = "ABCABC", str2 = "ABC"
輸出：“ABC”
範例2：
1
2
輸入：str1 = "ABAB", str2 = "ABAB"
輸出：“AB”
範例3：
1
2
輸入：str1 = "LEET", str2 = "CODE"
輸出：""
解題實作
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
public class Solution {
public string GcdOfStrings(string str1, string str2) {
//如果正反拼接一樣，就有公因子
if(str1+str2 != str2+ str1) return "";
//取得公因數
int gcd = GCD(str1.Length, str2.Length);
//回傳字串的最大公因字詞
return str1.Substring(0,gcd);
}
//使用「輾轉相除法」取得最大公倍數
private int GCD(int a, int b) {
//a除以b餘數為0，除數b就是最大公因數，否則就使用遞迴，自己呼叫自己
return (a % b == 0) ? b: GCD(b, a%b);
}
}
最大公因數
最大公因數（英語：highest common factor，hcf）也稱最大公約數（英語：greatest common divisor，gcd）是數學詞彙，指能夠整除多個整數的最大正整數。而多個整數不能都為零。例如8和12的最大公因數為4。
輾轉相除法 相比質因數分解法，輾轉相除法的效率更高。
計算gcd(18,48)時，先將48除以18得到商2、餘數12，然後再將18除以12得到商1、餘數6，再將12除以6得到商2、餘數0，即得到最大公因數6。我們只關心每次除法的餘數是否為0，為0即表示得到答案。