翼若垂天之云

按：数论貌似是我目前还接触太少的领域，遵从vls的推荐借了北大出版社的《简明数论》来浏览，还是很好玩儿的……下面是从中总结的一些比较新鲜的结论。

{a_i} 的最大公约数等于 {a_i} 的所有整系数线性组合组成的集合中的最小正整数；

事实上，被最大公约数整除，等价于能表示成整系数线性组合。

一次不定方程 ∑a_i*x_i=c 有解的充要条件是 c|({a_i})；

解一次不定方程的算法（待实现）。

x^2+y^2=z^2 的本原解：x=r^2-s^2, y=2rs, z=r^2+s^2；

其中r>s>0, (s,r)=1, 2不整除r+s；
等价地刻画了单位圆周上的有理点。

Chebyshev不等式：，；

其实重点在于：O(π(x))=x/log x，O(p_n)=n log n。

（π(x)即不大于x的素数个数；p_n即第n个素数。）

数论函数：[完全]积性函数的充要条件；

除数和函数；
F(n)=∑_{d|n}f(d) 保持f(n)的积性。（除数即Divisor）

Mobius函数：；

事实上与容斥原理很有关联；
引理：

集合A中与K互质的元素个数，其中A_d是A中被d整除的子集；
将A取不超过x的实数，K取不超过的所有素数的乘积，可得，这样可以在已知不超过的素数的前提下求π(x)。

从算法的角度看似无意义？

Tags: 书籍, 数学, 数论

Related posts

悲剧因何发生？
我没见过这般纯美的爱情
迷茫 [20080527]
行装
听合唱音乐会有感及其它

每个或有或无意义的开始，我都会变得兴奋而躁动，一些忘却抛弃，一些憧憬期许。就像今年一月我无理由地坚定地认为2008年是美好的一年一样，七月的最初，我同样坚定地做出七八月的暑训、今年下半年以及整个大一的一年时光都将美丽姣好的没有理由的结论。——七月四日
过了二分之一的这个七月，给我的感觉不同于以往的任何一个时期。——极度繁复的同时，也极度简约。极度火热的同时，又极度冷寂。贯穿每日的主线是，一边拼命挣钱、一边拼命花钱，一边努力出题、一边努力做题，一边尽力提高自己、一边尽力指导别人。就是这样，若非亲历很难体会。
集训前两周期已经结束的六场比赛需要总结一下。
Contest 2 by Balloon 是没进行任何ACM/ICPC有关的活动几十天之久后第一次比赛，完全没状态，Rank 12。依序看到D，便知道该怎么做了，19 min 1Y，是全场第一个AC此题的。看到有两人AC了A，略思考便想到了跟NOI某题类似的做法。当时认为，精度的缘故，需要写一个分数类，很快的敲完了。后来的事实证明，我现场敲的分数类对负数的处理有极大漏洞。可我错误地估计了错误，一遍遍地在主程序中寻找bug，WA无数次才意识到是分数类写得有问题。后来我发现，只要把我第一次提交的很垃圾的程序加上两行补丁，就可以AC。现场在66min交到第九次才AC的原因，一是一开始错误地估计了bug的位置，二是正确地找出bug以后没有仔细思考就开始写较为复杂的补丁，而没有看清错误的本质所在。这两个题水过以后，看上去可做的题目有B和E。对于B，我非常怀疑自己此时的coding能力能否应对这个算法不难代码似乎不好写的题目，于是看E，这个我最终交了13次也没AC的题目。交了4次E，完全不知道为什么WA，放弃了。然后开始很慢的写B，写一种极度麻烦的算法，一直到145min才交了两次AC。再次概览剩下的题目，仍然认为只有E可做，拼命查错和提交，一直到比赛结束都无果。最终才明白，原来E是因为误解了scanf中”\n”的意思，导致读入出错了……交的第二个程序的算法就是完全无误的。如果能更早地做掉E，显然与它的加强版F题不存在AC的障碍。真没想到算法一点问题都没有还会败在输入上……
Contest 3 by Cannon 也是一场郁闷的比赛，Rank 8，虽然Rank有所上升，但是题数上非常不满意，只有两题，是第一名的三分之一。陷入两个大坑，是做过的所有比赛中最郁闷的一次。看了A就觉得可做，不过大概由于慢热的缘故，26min时交到第4次才AC，原因主要是coding时欠考虑吧。又看了B和C，B觉得略有麻烦，C似乎是裸的高精而已，就开始写大数类。看来是完全没有吸取上次手写分数类的教训，对自己当下的coding能力认识不足，大数类不是写错就是效率有问题。期间推了下B的式子，也AC了。在C还是没能AC的情况下，又陷入了F，记忆化搜索，WA无数。后来发现，我的算法和标程不一样，但也没找到实质性的错误。剩下的时间就是在疯狂地改和交C和F，无果。比赛结束前20min意识到C可以用模板，可惜对学校的大数模板完全不熟悉，C++中stream相关的内容也基本忘了，输入输出都有点搞不定……现在看来，这次比赛AC
题数过少的原因之一是我较为熟悉和擅长的DP一题都没出。见到的题目太少，略有些 ad hoc 的题目就会搞不定，这是目前最大弱点。
Contest 4 by Die 的感觉稍微好一点，Rank 5。35 min时一次AC了H，擅长的套路。然后67min时用了三次提交AC了G，算法完全正确，问题在于无视了题目中一个条件，导致两次WA。然后就看到很多人过了B，便也很容易地AC了，在此之前的一次提交竟然是MLE……原因是忘了输入完成以后break。下一道题的目标我选了E，交了9次基本都TLE以后，确定自己的算法错了，就中途离开机房吃饭去了。这场比赛做得太急，导致不细心。赛后觉得，如果更多地花点时间思考下D，是应该能搞出来的，错误地估计了其难度与麻烦程度。
第一轮完毕以后，计罚时和不计罚时的rank分别是9和11。
第二轮，从 Contest 5 by Balloon 开始，逐步有了状态，Rank 3，比赛过程可称顺利。一开始看到了B，觉得是一般难度的DP，随手写了交上去，然后WA。静下来看一下，发现整个算法是错的，换了正确的算法重写，结果疏忽了一句保持单调性的话，交到第三遍才AC。下面是E，非算法题，比较熟练地用着STL，1Y了。F又是一个DP，吸取教训仔细想清楚了才写，同样1Y。接下来做A的时候又卡了一下。最开始写的是搜索，没有估计好复杂度，TLE两次，第一次交TLE了以后还以为是被卡了常数，第二次TLE后算了下复杂度才意识到必须加上记忆化。加记忆化的时候又写错了一次，第四次才AC，属于失误。看到wanwei似乎很轻松的1Y了winsty的小蘑菇题G，虽然明知自己对这种题目根本不擅长，但也没发现有别的可做的题目了。写了很久，调了很久，花费了近一个小时，还好1Y了。在这一段过程中一直都是紧随Murphy，排名第二，看到他过了C，就也去搞。没想到一下子就看出了C的本质，用DP预处理一下后，又1Y了。这时，只剩下了一道没人碰的蘑菇题D，我怎么看都没信心，很累，又计算了一下发现后面的人不大可能超过来，就很高兴地提前近一个小时出去吃饭了。后来得知G的数据有小问题，rejudge了以后rank 2的位置变成了watashi。在题数上，应该说没有任何遗憾，1Y率有提高，很满意。
Contest 6 by Cannon 是目前位置的最好成绩，Rank 2，但是不像上次一样毫无遗憾，因为是由于不必要的失误没得到Rank 1。前一天晚上只睡了五个小时不到导致状态很差。开场先做了矩阵题G，打算秒杀之，没想到一开始就因为矩阵乘法写得不太好而TLE两次，优化了效率以后又接连地WA，要郁闷死了。到论坛里看了答疑才知道原来自己把题意理解错了，改之即AC。91min第7次才AC这题，真是开场不利。AC了G以后开始做C，很老的题，用匹配做，没想到竟然WA。难道自己已经退化到连Hungary这样简单的算法都会写错？很沮丧，就暂时放下了。看到A是不难的DP。哦……好吧，对于我来说不难的DP，WA一次以后AC了，WA的原因是没看清题……寒。把手放在键盘旁的圣经上，定神了以后做C，一个不太难的搜索题，终于一次AC。接下来的时间就在搞C，出很多组数据来测，怎么都看不出为何会WA……这时看到自己是Rank 2，3题的两人之一，但由于罚时太多太多后面的人很有可能超过来。十一点一刻的时候最后交了一次WA终于放弃了，因为实在是找不到错误，加上极其瞌睡，就跑掉了。没想到但是直到结束竟然能保持住Rank 2的位置。后来得知，C是因为输入处理错了导致不断WA。竟然又是该死的scanf里面的”\n”，第三道题了！所以太遗憾了……真不应该那么早离开的。以后再遇到这种莫名其妙的WA一定要仔细验证下输入输出。
Contest 7 by Die 打破了前五场Rank单调递减的神话，Rank 6。做得不够好，罚时太多了，而且策略有失误。开场以后大致看了一遍题，发现A是可做的DP，虽然有点麻烦。写了四十多分钟，交上去WA。惊讶地发现这时AC两题的都有了，都是B和E，E有十几个AC的。意识到E是第一遍没看出来的极水的题，随便一写就1Y了。又去做A，又WA一次，发现没看清题，53min第三次提交才AC了。接下来当然是做B，做的过程很不顺利。一开始发现搜索可做，经历了MLE、TLE和两次WA以后，对搜索有些绝望了。惊奇地发现用匹配可做，粘贴了任意图匹配的模板，终于很不容易地AC了。事实上这题完全可以用搜索，是我一开始写丑了。接下来的目标我锁定在D上，自以为对这类最优比率的题目非常熟悉，不就是二分答案么。虽然写起来也有点繁，不过还是很有信心地在写。写完以后，就总是WA，发现我的Bellman-Ford总是莫名其妙地找不到负环……在那边拼命地调啊改啊，基本上各种可能的错误返回都经历了一遍，还是没能AC。期间发现比我多一题的都是AC了F，但是F使我非常不熟悉的类型，完全没法形成完整的思路。到了只剩一个小时的时候，我终于放弃了搞了一个半小时的D，开始硬着头皮写思路还想不清楚的F，加上这时已经很累了，一直到比赛结束还没调出样例来……罚时太多就不说了，看错题写错代码还可以解释成状态不好。关键是，这场比赛的策略太失误了！像A那么麻烦的DP显然不应该作为第一道题来做，要相信肯定会有比这水的题嘛，这直接导致了E和B的用时比正常值多多了。至于D，后来知道，应该用迭代法做的。自己不会这个方法，AC不了，也没什么不正常。但问题就在于，D搞了那么长时间，交了24次，实在有些过于固执了。虽然E是我不熟悉的类型，但毕竟是非常可做的题，那么多人都AC了，只要有时间慢慢搞应该不存在问题的，至少完全可以写个复杂度略高但好写很多的算法。唉，还是经验少，太莽撞。
第二轮结束以后，计罚时和不计罚时的Rank都是6。
~~~~以下是三、四轮的总结~~~~、
Contest 9 by Cannon，一场有失误、没遗憾的比赛，Rank 6。开场扫了一遍题，没发现特别秒杀的，就开始写F，一道简单的树的题，轻松1A。不久后又有人过了A，属于经典问题。一开始没想清楚算法，WA了，又因 为忘了删掉调试语句Output Limit Exceeded了一次（第一次得到这种返回的说- -）。好在第三次提交就AC了。这时有一些人过了C，一个小蘑菇题。这种题我也掌握了一些诀窍了，就是不厌其烦地尽量结构化，让自己能掌握全局的思路，就 可以了。似乎用了十多分钟就很高兴地AC了这题。E是一个数论题，略加考虑写了一个递推求欧拉函数的程序，还不厌其烦地加了很多优化，没悬念地AC了。这 时，比赛开始才一个半小时，我AC了4题，速度都很快，排名第一位。这时，D那种蘑菇题我显然是不写的，F可以看出来是搜索可怎么分析都会TLE（后来知 道标程是IDA*)。可做的题目只剩下B，一个背包问题的变体。我yy了一会儿，发现自己可能“证明”了，可以将一种规模一定不可做的01背包问题规约到 这个题，所以说，这题一定不可做了！我甚至抱定了“标程的算法是错的”这样的信念。加上我很期盼的快件到了，便很潇洒地离开了机房。当然，当时“规约”的 证明是完全错误的，属于失误了。最后有五个人很艰难地搞出了B题，我就排到了第六，不过也没什么遗憾的。呵呵，恐怕我觉得不遗憾的原因之一是我离开机房以 […]

前两天期末考试结束了，一下子就感到满心的轻松自在。虽然逐步公布的成绩不断刷新着低分记录，但至少担心挂科的危险已经没有了。不愉快的事情几乎已经遗忘过去，我再次表现出了不想记得的事就能迅速抛到脑后的优良品质，没心没肺惬意地活着。
考试完了以后，就一直在准备家教的最初几节课，还在非常认真地做ppt：简要介绍OI、讲解初赛知识、C语言的Hello World……很繁琐呢。听说大多做一对一家教的人都不做ppt直接讲的？反正我是打算要做就做到极致和完美。也就是说，我打算做的工作量，基本等于自己写一本完善的从零开始的NOIP辅导教程。不过，那不是我一直想做的事情吗？教育是高尚的事情。虽然还没正式开始，发现自己已经很热爱这件事情了呢！后天去第一次试讲，我知道那会很成功的。
这学期上的C语言课程，期末可以编写“大型程序”赢取额外的加分。我编了一个“表达式解析计算器”，可以完成基本的四则运算、科学计算等，还会绘出表达式树（调用graphviz），被助教评为95分。有兴趣的可以下载来看一下，包含完整的源码、Win32可执行程序以及文档。其中我的代码没有什么license，可以拿去任意使用。
放假了，blog 的风格会转为少量多次的即时更新。

Tags: C语言, NOIP, 家教, 成绩, 期末

Related posts

在郑州
ACM新手上路总结及感言

这几天经历众所不太周知的变故和打击，再加上人际关系、期末考等方面的压力，几乎就会崩溃了。
每天和挚友通很长时间电话聊天，在电脑上做很多很无聊的事情，也许只是为了避免静下来细想种种。
好在，好在，除了亲人以外，还有人会无条件地支持我、相信我、鼓励我。让我在这一个人的孤岛，感受到温暖，与感动。
刚才，宋晨姐姐就要离开了，还会想起我，送我那么多东西，多想和她长谈，虽然也许再也没有机会。还有的朋友，会很小心地避免提起让我伤心的字眼，会故意地把话题转移到那些让我激动欢乐的成功经历和辉煌时刻，为了我他们多么良苦用心。
谢谢你们。我保证我会振作。
~~~~~~~~下一段无关主题的分割线~~~~~~~~
许飞《恰许同学年少》。我从来都是喜欢有特点的女声，以及女生。顺便说下，那句“写一首淡淡的歌给你丫（呀）”我听来其囧无比，每听必喷饭。
在听 Rubinstein 的 The Chopin Collection，11CD。随便听了一首 Nocturne之后，我就发现，以前听的 Chopin 都白听了。以前的我一直是只注重作品，忽视演奏者和版本之类。阴差阳错地，竟然从未听到过坊间所称“最正宗的” Robinstein 演绎的 Chopin。一听之下，惊为天人。与其他人相较，我认为 Rubinstein 的演绎既有弹性、不过火，又有激情、蕴涵力量，拿捏得恰到好处。不过 Rubinstein 好像没演奏过革命练习曲（Etudes in C Minor, Op. 10 No. 12 “Revolutionary”），我最喜欢的作品之一，小小遗憾。
看了1999年的影片版 Animal Farm。大约是制作班底的功力原因，力量远不如原著。不过，影片自有文本不能代替的表现力，仍然有令人睁大眼睛思考的片段：巨大的 Napoleon 塑像，俄罗斯风格的革命歌曲，双足站立着西装的猪，都让人难忘。如果像我一样是 George Orwell 以及 Animal Farm 的 fans，这种周边产品自然是非看不可的。没看过原著的，强烈推荐仔细读一下 Animal Farm 的英文原著。
听了郭静的专辑《下一个天亮》。起初没什么感觉，后来几乎沉浸在那旋律中不能自拔。的确很少听过这种描写爱情的歌曲了，那词曲不经意间就触动了什么。还有袁泉《孤独的花朵》，很文艺，很唯美，很好听。
买了不少东西，漫步者的耳塞H180，和耳机H500。本来想买森记MX500、PX200之类的东西，后来想通了，花那么多钱干嘛，支持国产品牌。果然，性价比让我非常满意，对于我这种只是用电脑和手机听音乐的人来说已经相当足够了。还缺一个隔音好的入耳，漫步者H260上百的价钱我看来有点贵了，有人给推荐没？
在淘宝商城买了美的电动牙刷MQ-Y21，用了一次就有点后悔。单独一个旋转刷头本来就是比较初级的设计，如果卖50元以下还比较容易接受。性价比也有点低，下次一定买欧乐B。不过，话说估计任何一种电动牙刷都要比我自己刷得干净。
看了《三体II：黑暗森林》，很震撼。感觉大刘的文风和想象力都比写第一部时成熟、完整了许多，这本书带给我的是远超《三体I》的震撼。当然，也许是因为看第一部时是一段一段地看连载，没有完整地看，导致没有这么好的印象吧。
看了纪录片《森林之歌》的一个精编版。说来惭愧，以前基本没看过这种自然风光题材的纪录片。看了以后，一下子发现，自己作为人类的一员，以前都是以这个星球当仁不让的唯一主人自居的。了解了一点神奇的自然，就开始对以前的那种唯我独尊感到羞愧。打算逐步多看一点此类纪录片，比如最近的 Wild China 以及国家地理之类，为进一步谦卑，为心灵的平和与自如。
再次欣赏了很久以前就听过的唱片《我的海洋》，宽阔。
~~~~~~~~逐步平静与集中的分割线~~~~~~~~
接了一份暑假的OI家教，加上集训，这个假期注定是紧张忙碌热火朝天的。下学期的十五门课，也强迫自己不能不努力调整学习状态。
生活在继续，我也一样。

Tags: Chopin, 三体, 动物庄园, 女声, 我的海洋, 电动牙刷, 纪录片, 耳机

Related posts

悲剧因何发生？

再有几个小时，牵动人心的高考就要拉开序幕了。非常高兴地逃过此劫。在此 bless all，尤其祝福梦想是浙大的同学。
昨天凌晨，Google Reader 上这个 blog 的订阅量达到了三位数。感谢大家的捧场，我会坚持如此的无主题随性路线。
不小心把 Gmail 里给 Fire 的回复点成了 “Reply to All”，导致集训队的所有人都收到了，在此再次道歉。嗯……道歉是诚恳滴，bg 是没可能滴。
~~~~~~~~诚恳道歉的分割线~~~~~~~~
这段时间仍然听了不少音乐，可惜没有令人惊艳的。值得一提的：奥戸巴寿的《ピアノによる珠玉のアニメ映画主題歌集「いつも何度でも_もののけ姫」》，在宫崎骏动画中的钢琴配乐；女子十二楽坊的《ベスト》，了解这个乐团的最佳精选集。
看了几部宫崎骏的动画：哈尔的移动城堡、天空之城、千与千寻、魔女宅急便，全都很值得推荐，以前常看的 Pixar、DreamWorks 完全不同的风格，第二个和第三个强力推荐，打算逐步看完全集。
V for Vendetta，昨天看的，感觉无法用言语表达，只是推荐没看过的人找来看看吧。
期末考试很近了，上网时间减少，这个月没什么大事不会再更新。七月ACM暑期集训，应该会出现一批算法方面的精品内容。
累了，去睡了。

Tags: Google Reader, V for Vendetta, 动画, 宫崎骏, 电影, 音乐, 高考

Related posts

最近乐思频发
水晶心伴奏[.mid][超粗糙第一版]
六一荐碟
一阕歌伤
08年5月11日至12日