整理东西的时候翻看以前的笔记，看到当初讲座owen讲的一个题，这题当时不会，今天突然来了兴致给做了。
　　给定一个a * b的网格，从左下到右上画一条线穿过的格子数是n。给定一个n问有多少种不同的a和b满足穿过的格子数为n。对应TJU 2880。
　　首先n = a + b - gcd(a, b)。因为对于每个穿过的格子，直线可能会从格子的上侧穿过，也可能从格子的右侧穿过，也可能既穿过上侧也穿过右侧(也就是从右上角穿过)。因为直线总要从左边走到右边，因此恰好有a个格子会被直线穿过右侧(直线是连续的，不会在同一列同时穿过两个格子的右侧)，同理恰好有b个格子会被直线穿过上侧，这样总共就是a + b个。但是这样的话穿过右上角的格子就被重复计算了，这样的格子如果坐标为(x, y)，一定满足这个条件：x : y = a : b，这样ay = bx，显然满足等式的解个数是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')的个数，求和就是结果。接下的问题就是求a' + b' = n'的序对个数。可以认定gcd(a', n') = 1，如果不是这样的话，会有a' = t * A, n' = t * N, 这样的话b' = t(N - A)，这样就和a'、b'互素矛盾。这样只需要求和n'互素的数的个数即可，利用欧拉函数就可以很高效的找到满足条件的序对个数了。