整理東西的時候翻看以前的筆記，看到當初講座owen講的一個題，這題當時不會，今天突然來了興致給做了。
　　給定一個a * b的網(wǎng)格，從左下到右上畫一條線穿過的格子數(shù)是n。給定一個n問有多少種不同的a和b滿足穿過的格子數(shù)為n。對應TJU 2880。
　　首先n = a + b - gcd(a, b)。因為對于每個穿過的格子，直線可能會從格子的上側穿過，也可能從格子的右側穿過，也可能既穿過上側也穿過右側(也就是從右上角穿過)。因為直線總要從左邊走到右邊，因此恰好有a個格子會被直線穿過右側(直線是連續(xù)的，不會在同一列同時穿過兩個格子的右側)，同理恰好有b個格子會被直線穿過上側，這樣總共就是a + b個。但是這樣的話穿過右上角的格子就被重復計算了，這樣的格子如果坐標為(x, y)，一定滿足這個條件：x : y = a : b，這樣ay = bx，顯然滿足等式的解個數(shù)是gcd(a, b)個。這樣n的值就被計算出來了。
　　然后設g = gcd(a, b)，a = a' * g, b = b' * g, 那么n = (a' + b' - 1) * g, 其中gcd(a', b') = 1。通過枚舉g可以求出滿足條件的(a', b')的個數(shù)，求和就是結果。接下的問題就是求a' + b' = n'的序對個數(shù)。可以認定gcd(a', n') = 1，如果不是這樣的話，會有a' = t * A, n' = t * N, 這樣的話b' = t(N - A)，這樣就和a'、b'互素矛盾。這樣只需要求和n'互素的數(shù)的個數(shù)即可，利用歐拉函數(shù)就可以很高效的找到滿足條件的序對個數(shù)了。