随笔 - 68  文章 - 57  trackbacks - 0
<2010年4月>
28293031123
45678910
11121314151617
18192021222324
2526272829301
2345678

常用链接

留言簿(8)

随笔分类(74)

随笔档案(68)

搜索

  •  

最新评论

阅读排行榜

评论排行榜

  整理东西的时候翻看以前的笔记,看到当初讲座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'互素的数的个数即可,利用欧拉函数就可以很高效的找到满足条件的序对个数了。

posted on 2010-04-26 23:34 sdfond 阅读(339) 评论(0)  编辑 收藏 引用 所属分类: Algorithm - Number Theory

只有注册用户登录后才能发表评论。
网站导航: 博客园   IT新闻   BlogJava   知识库   博问   管理