題目連結：
題目大意：
給定兩正整數 N 、 K （1 ≦ K < N ≦ 10 ^ 15），代表有 N 顆球圍成一個圓形（這些球衣開始都是白的）。定義兩球的距離為：中間隔著 M - 1 顆球，則距離為 M。
試問最多可以將多少球塗成黑色，使得任兩個黑球之距離（因為是圓的，所以距離會有兩個：順時針以及逆時針）都不為 K ？
範例輸入：
範例輸入 1:
6 2
範例輸入 2:
10 3
範例輸出：
範例輸出 1 :
2
範例輸出 2 :
5
解題思維：
觀察以下 N ＝ 12 在不同 K 值最多黑球（用較明顯的藍色表示，而不是真的黑色）的情況：
（注：雖然是用一整列的Ｏ表示，但是不要忘記首尾是相連的）
K ＝ 1
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 2
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 3
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 4
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 4 顆
K ＝ 5
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 6
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 7
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 8
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 4 顆
K ＝ 9
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 10
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
K ＝ 11
ＯＯＯＯＯＯＯＯＯＯＯＯ
最多： 6 顆
如果仔細觀察，可以看到上面的每個 K 值中的每「群」黑球（也就是連在一起的那些黑球）之間的間隔是 N 與 K 的最大公因數 g（除了 K = 4 、 8 的情況較特別），且每群黑球也剛好都是 g 個球。
定 g = GCD(N, K) 並按照以下方式去填會是最佳的：
Ｘ……ＸＯ……ＯＸ……ＸＯ……Ｏ……
其中，每「群」的Ｘ以及Ｏ都是各 g 個。
可以看到每個黑球都盡量地靠近，且往左或往右 g 顆球（即原本的順時針、逆時針的距離）都不是黑色的球。因為 g 根據定義，是 N 與 K 的最大公因數，因此 g 保證會是 N 的因數，也因此從黑色的球群出發往左或往右 g 顆球保證只會落在白色球群。
那麼對於 N = 12 ， K = 4 、 8 的情況分別是怎麼樣呢？其實也是類似於上面的狀況，但是結尾的部分跟別人不太一樣。我們將那兩個情況各自將結尾的四顆球剔除（以灰色和刪除線表示）：
K ＝ 4
ＯＯＯＯＯＯＯＯＯＯＯＯ
K ＝ 8
ＯＯＯＯＯＯＯＯＯＯＯＯ
可以看到實際上也有出現了各自一群的黑球與白球間隔（如同上面其他 K 值的狀況）。但是因為結尾各自都只剩 4 顆球，不足以產生新的黑球群（如果硬是塗上黑色的話，就會與前面的黑球有著距離 K），所以這 4 顆只能是白的。
而實際上只會出現剛好或是結尾多出恰好 g 顆白球的情況（同樣也是因為 g 是 N 、 K 的最大公因數）。
因此，我們只需要先算出 N 、 K 的最大公因數 g 。再看可以分成幾組黑球、白球群相隔，即 g 個黑球接著 g 個白球再接著 g 個黑球並接著 g 個白球……，最後將組數乘以 g （因為每個黑球群接著白球群這樣子的組別各有 g 個黑球）即是所求。
此次分享到此為止，如有任何更加簡潔的想法或是有說明不清楚之地方，也煩請各位大大撥冗討論。
達人