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