題目連結：
題目大意：
給定兩個二進位數字（長度不超過１００００００），求兩數的最大公因數（以二進位表示）。
解題思維：
觀察任意兩個二進位數字（以下稱Ａ、Ｂ，且Ａ ≧ Ｂ），得：
當Ａ、Ｂ的尾數為０時，最大公因數也會有０作為結尾，因此（除以２意指刪除尾數）
ＧＣＤ（Ａ, Ｂ）＝ＧＣＤ（Ａ / ２, Ｂ / ２）＋「０」作結尾。
當Ａ尾數為１、Ｂ尾數為０時，最大公因數不會有０，得
ＧＣＤ（Ａ, Ｂ）＝ＧＣＤ（Ａ, Ｂ / ２）
當Ａ尾數為０、Ｂ尾數為１時，最大公因數也不會有０，故
ＧＣＤ（Ａ, Ｂ）＝ＧＣＤ（Ａ / ２, Ｂ）
當兩數尾數皆為１時，最大公因數便可以透過輾轉相除法（這邊只有用減的）。又因兩數皆為奇數（是二進位數字且尾數為１，而為奇數），所以互減之結果必為偶數。但根據上面的情況，一奇一偶又可以對偶數那方除以２，所以
ＧＣＤ（Ａ, Ｂ）＝ＧＣＤ（Ａ, （Ａ－Ｂ）/ ２）
而不需多說，Ａ＝Ｂ時，最大公因數即為彼此。
以第１～４條規律作為遞迴條件，並以最後一條作為終止條件，即可找到所需之答案。
達人